Symmetric Perceptrons, Number Partitioning and Lattices
Neekon Vafa, Vinod Vaikuntanathan · 2025
Read Symmetric Perceptrons, Number Partitioning and Lattices by Neekon Vafa, Vinod Vaikuntanathan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-16517.txt.
Introduction
Neekon Vafa and Vinod Vaikuntanathan prove that two classic average case puzzles are nearly as hard as theory long suspected, in work from twenty twenty-five. The symmetric binary perceptron asks for a sign vector that keeps a random matrix product tightly bounded. Number partitioning is its one row special case.
Both problems show a wide gap between what statistics allows and what fast algorithms reach. The best known perceptron method hits a known bound, and a recent conjecture said it cannot be beaten. Vafa and Vaikuntanathan prove that conjecture, assuming a standard hard lattice problem stays hard. For partitioning, the classic differencing method is likewise nearly optimal under the same assumption.
Catalog record
| CREATOR | Neekon Vafa, Vinod Vaikuntanathan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-16517
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Symmetric Perceptrons, Number Partitioning and Lattices Neekon Vafa, Vinod Vaikuntanathan Abstract The symmetric binary perceptron ( SBP κ \mathrm{SBP}_{\kappa} ) problem with parameter κ : ℝ ≥ 1 → [ 0 , 1 ] \kappa:\mathbb{R}_{\geq 1}\to[0,1] is an average-case search problem defined as follows: given a random Gaussian matrix 𝐀 ∼ 𝒩 ( 0 , 1 ) n × m \mathbf{A}\sim\mathcal{N}(0,1)^{n\times m} as input where m ≥ n m\geq n , output a vector 𝐱 ∈ { − 1 , 1 } m \mathbf{x}\in\{-1,1\}^{m} such that ‖ 𝐀𝐱 ‖ ∞ ≤ κ ( m / n ) ⋅ m . ||\mathbf{A}\mathbf{x}||_{\infty}\leq\kappa(m/n)\cdot\sqrt{m}~. The number partitioning problem ( NPP κ \mathrm{NPP}_{\kappa} ) corresponds to the special case of setting n = 1 n=1 . There is considerable evidence that both problems exhibit large computational-statistical gaps. In this work, we show (nearly) tight average-case hardness for these problems, assuming the worst-case hardness of standard approximate shortest vector problems on lattices. • For SBP κ \mathrm{SBP}_{\kappa} , statistically, solutions exist with κ ( x ) = 2 − Θ ( x ) \kappa(x)=2^{-\Theta(x)} (Aubin, Perkins and Zdeborová, Journal of Physics 2019). For large n n , the best that efficient algorithms have been able to achieve is a far cry from the statistical bound, namely κ ( x ) = Θ ( 1 / x ) \kappa(x)=\Theta(1/\sqrt{x}) (Bansal and Spencer, Random Structures and Algorithms 2020). The problem has been extensively studied in the TCS and statistics communities, and Gamarnik, Kızıldağ, Perkins and Xu (FOCS 2022) conjecture that Bansal-Spencer is tight: namely, κ ( x ) = Θ ~ ( 1 / x ) \kappa(x)=\widetilde{\Theta}(1/\sqrt{x}) is the optimal value achieved by computationally efficient algorithms. We prove their conjecture assuming the worst-case hardness of approximating the shortest vector problem on lattices. • For NPP κ \mathrm{NPP}_{\kappa} , statistically, solutions exist with κ ( m ) = Θ ( 2 − m ) \kappa(m)=\Theta(2^{-m}) (Karmarkar, Karp, Lueker and Odlyzko, Journal of Applied Probability 1986). Karmarkar and Karp’s classical differencing algorithm achieves κ ( m ) = 2 − O ( log 2 m ) . \kappa(m)=2^{-O(\log^{2}m)}~. We prove that Karmarkar-Karp is nearly tight: namely, no polynomial-time algorithm can achieve κ ( m ) = 2 − Ω ( log 3 m ) \kappa(m)=2^{-\Omega(\log^{3}m)} , once again assuming the worst-case subexponential hardness of approximating the shortest vector problem on lattices to within a subexponential factor. Our hardness results are versatile, and hold with respect to different distributions of the matrix 𝐀 \mathbf{A} (e.g., i.i.d. uniform entries from [ 0 , 1 ] [0,1] ) and weaker requirements on the solution vector 𝐱 \mathbf{x} . 1 Introduction Symmetric Binary Perceptrons. The symmetric binary perceptron ( \mathrm{SBP}_{\kappa} ) problem, also called the symmetric Ising perceptron problem [ JH60 , Win61 , Cov65 , APZ19 , BDVLZ20 , PX21 , ALS21 , ALS22 , GKPX22 , GKPX23 , BEAKZ24 ] , is a search problem defined as follows: given a random matrix \mathbf{A}\sim\mathcal{N}(0,1)^{n\times m} with entries chosen i.i.d. from the normal distribution where m\geq n , find a binary vector \mathbf{x}\in\{-1,1\}^{m} such that \left\|{\mathbf{A}\mathbf{x}}\right\|_{\infty} is minimized. More formally, SBP with parameter \kappa:\mathbb{R}_{\geq 1}\to[0,1] asks us to find an \mathbf{x}\in\{-1,1\}^{m} such that \left\|{\mathbf{A}\mathbf{x}}\right\|_{\infty}\leq\kappa(m/n)\cdot\sqrt{m}~. Here, the quality of the solution is parameterized as a function of m/n , the so-called (inverse) aspect ratio of the problem. 1 1 1 The notation commonly used in the literature to parameterize \mathrm{SBP} (and \mathrm{NPP} ) is slightly different than the notation we choose to use. The aspect ratio is given by \alpha=n/m , and instead of writing \kappa as a function of \alpha (or really, x=1/\alpha , as we do), the roles are flipped, where \alpha is a function of \kappa . For example, \kappa(x)=2^{-x} and \kappa(x)=1/\sqrt{x} , in our notation, correspond to \alpha(\kappa)=1/\log_{2}(1/\kappa) and \alpha(\kappa)=\kappa^{2} in the notation of [ GKPX22 ] , respectively. The problem is versatile, and can be defined with respect to different distributions of the matrix \mathbf{A} (i.i.d. uniform [0,1] entries is another popular choice) and different requirements on the solution vector \mathbf{x} . The problem also has rich connections to several other fields including the classical subset sum problem and its variants and the problem of discrepancy minimization. Two natural questions arise: a statistical question and a computational one. The statistical question asks for which \kappa do solutions exist (with high probability over the choice of the matrix \mathbf{A} ). Recent works by Aubin, Perkins and Zdeborová [ APZ19 ] , Perkins and Xu [ PX21 ] , and Abbe, Li and Sly [ ALS21 ] showed sharp statistical thresholds for this problem. In particular, they showed that the threshold for the existence of solutions is \kappa_{\mathsf{stat}}(x)=O(2^{-x}). On the other hand, the best solutions found by polynomial-time algorithms satisfy \kappa_{\mathsf{comp}}(x)=\Omega\left(\frac{1}{\sqrt{x}}\right). This comes from the breakthrough work of Bansal [ Ban10 ] and Bansal and Spencer [ BS20 ] from the closely related field of combinatorial discrepancy theory. 3 3 3 Their result is established for the case of matrices \mathbf{A} with i.i.d. Rademacher entries. Nevertheless, [ GKPX22 ] conjecture that the same guarantee remains true for the case of i.i.d. standard normal entries. Gamarnik, Kızıldağ, Perkins and Xu [ GKPX22 , GKPX23 ] studied the large statistical-computational gap scenario in detail and conjectured that no polynomial-time algorithms can achieve a guarantee much better than \kappa_{\mathsf{comp}}(x) . In particular, they show that the so-called overlap gap property [ MMZ05 , AR06 , Gl16 ] , which rules out a class of stable algorithms, sets in at \kappa_{\mathsf{overlap}}(x)=O\left(\frac{1}{\sqrt{x\log x}}\right). We refer the reader to [ GKPX22 ] for an extensive discussion of the rationale behind their conjecture. A survey of Gamarnik on the overlap gap property [ Gam21 ] points to the question of whether average-case hardness of perceptron problems (and more) can be based on worst-case hardness assumptions. Gamarnik explicitly states that worst-case to average-case reductions for these problems “would be ideal for our setting, as they would provide the most compelling evidence of hardness of these problems” [ Gam21 ] . The first contribution of this work is a proof of the conjecture of [ GKPX22 ] upto lower order terms, under the assumption that standard, well-studied, lattice problems are hard to approximate in the worst case. Theorem 1 (Informal version of Corollary 2 ) . Let \varepsilon>0 be any constant. Assuming that {\gamma} -approximate lattice problems in n dimensions with \gamma(n)=n^{O(1/\varepsilon)} are worst-case hard for polynomial-time algorithms, \mathrm{SBP}_{\kappa} with \kappa(x)=\frac{1}{x^{1/2+\varepsilon}} is hard for polynomial-time algorithms. Additionally, assuming near-optimal worst-case hardness of lattice problems, we obtain near-optimal hardness of SBP. In particular, assuming that \gamma(n) -approximate lattice problems require 2^{\omega(n^{1/2-\varepsilon})} time to solve in the worst case with \gamma(n)=2^{n^{1/2-\varepsilon}} , we have that \mathrm{SBP}_{\kappa} with \kappa(x)=\frac{1}{\sqrt{x}\cdot(\log x)^{c}} is hard for some constant c>1 . Lattice problems such as the shortest vector problem and the shortest independent vectors problem have been extensively studied for decades largely for their implications to combinatorial optimization [ LLL82 , Kan83 , Kan87 , RR23 ] and even more so, to cryptography [ Ajt96 , MR07 , Reg09 ] . Time-approximation tradeoffs for lattice problems are well-known [ Sch87 ]