2025/01/27 by Neekon Vafa, Vinod Vaikuntanathan, Vafa, Neekon +1 · 3 citations
Computer Science · #Advanced Algebra and Logic
paper · pdf · doi:10.48550/arxiv.2501.16517
The symmetric binary perceptron (SBPκ) problem with parameter κ: ℝ≥1 → [0,1] is an average-case search problem defined as follows: given a random Gaussian matrix A ∼ N(0,1)n × m as input where m ≥ n, output a vector x ∈ \-1,1\m such that || A x ||∞ ≤ κ(m/n) ⋅ √(m)~. The number partitioning problem (NPPκ) corresponds to the special case of setting 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, for large n, the best that efficient algorithms have been able to achieve is κ(x) = Θ(1/√(x)) (Bansal and Spencer, Random Structures and Algorithms 2020), which is a far cry from the statistical bound. The problem has been extensively studied in the TCS and statistics communities, and Gamarnik, Kizildag, Perkins and Xu (FOCS 2022) conjecture that Bansal-Spencer is tight: namely, κ(x) = \widetildeΘ(1/√(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, Karmarkar and Karp's classical differencing algorithm achieves κ(m) = 2-O(log2 m)~. We prove that Karmarkar-Karp is nearly tight: namely, no polynomial-time algorithm can achieve κ(m) = 2-Ω(log3 m), once again assuming the worst-case subexponential hardness of approximating the shortest vector problem on lattices to within a subexponential factor.