Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.16517 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- The symmetric binary perceptron ($\mathrm{SBP}_κ$) problem with parameter $κ: \mathbb{R}_{\geq1} \to [0,1]$ is an average-case search problem defined as follows: given a random Gaussian matrix $\mathbf{A} \sim \mathcal{N}(0,1)^{n \times m}$ as input where $m \geq n$, output a vector $\mathbf{x} \in \{-1,1\}^m$ such that $$|| \mathbf{A} \mathbf{x} ||_{\infty} \leq κ(m/n) \cdot \sqrt{m}~.$$ The number partitioning problem ($\mathrm{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 $\mathrm{SBP}$, for large $n$, the best that efficient algorithms have been able to achieve is $κ(x) = Θ(1/\sqrt{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/\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 $\mathrm{NPP}$, Karmarkar and Karp's classical differencing algorithm achieves $κ(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)}$, once again assuming the worst-case subexponential hardness of approximating the shortest vector problem on lattices to within a subexponential factor.