Category: cs.CC
-
Low-Degree Method Fails to Predict Robust Subspace Recovery
Low-Degree Method Fails to Predict Robust Subspace Recovery arXiv:2603.02594v1 Announce Type: new Abstract: The low-degree polynomial framework has been highly successful in predicting computational versus statistical gaps for high-dimensional problems in average-case analysis and machine learning. This success has led to the low-degree conjecture, which posits that this method captures the power and limitations of…
-
Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets
Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets arXiv:2511.20888v1 Announce Type: new Abstract: This paper argues that DNNs implement a computational Occam’s razor — finding the `simplest’ algorithm that fits the data — and that this could explain their incredible and wide-ranging success over more traditional statistical methods. We start…
-
Rate-optimal community detection near the KS threshold via node-robust algorithms
Rate-optimal community detection near the KS threshold via node-robust algorithms arXiv:2511.16613v1 Announce Type: new Abstract: We study community detection in the emph{symmetric $k$-stochastic block model}, where $n$ nodes are evenly partitioned into $k$ clusters with intra- and inter-cluster connection probabilities $p$ and $q$, respectively. Our main result is a polynomial-time algorithm that achieves the minimax-optimal…
-
Circuit Complexity Bounds for Visual Autoregressive Model
Circuit Complexity Bounds for Visual Autoregressive Model arXiv:2501.04299v1 Announce Type: new Abstract: Understanding the expressive ability of a specific model is essential for grasping its capacity limitations. Recently, several studies have established circuit complexity bounds for Transformer architecture. Besides, the Visual AutoRegressive (VAR) model has risen to be a prominent method in the field of…