2022/05/04 by Dylan J. Altschuler, Altschuler, Dylan J. · 4 citations
Computer Science · Mathematics · #Combinatorics (math.CO) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Mathematical Approximation and Integration #Mathematical Physics (math-ph) #Probability (math.PR) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2205.02319
openalex publication_date 2022/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the critical window of the symmetric binary perceptron, or equivalently, combinatorial discrepancy. Consider the problem of finding a binary vector σ satisfying ‖Aσ‖_∞ ≤ K, where A is an αn × n matrix with iid Gaussian entries. For fixed K, at which densities α is this constraint satisfaction problem (CSP) satisfiable? A sharp threshold was recently established by Perkins and Xu, and Abbe, Li, and Sly , answering this to first order. Namely, for each K there exists an explicit critical density αc so that for any fixed ε> 0, with high probability the CSP is satisfiable for αn < (αc - ε) n and unsatisfiable for αn > (αc + ε) n. This corresponds to a bound of o(n) on the size of the critical window. We sharpen these results significantly, as well as provide exponential tail bounds. Our main result is that, perhaps surprisingly, the critical window is actually at most O(log n). More precisely, with high probability the CSP is satisfiable for αn < αc n -O(log n) and unsatisfiable for any αn > αc n + ω(1). This implies the symmetric perceptron has nearly the "sharpest possible transition," adding it to a short list of CSP for which the critical window is rigorously known to be of near-constant width.