2023/02/13 by David Gamarnik, Eren C. Kızıldağ, Gamarnik, David +5 · 6 citations
Computer Science · Engineering · Materials Science · #Advanced Numerical Analysis Techniques #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Machine Learning in Materials Science #Mathematical Physics (math-ph) #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2302.06485
openalex publication_date 2023/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For many computational problems involving randomness, intricate geometric features of the solution space have been used to rigorously rule out powerful classes of algorithms. This is often accomplished through the lens of the multi Overlap Gap Property (m-OGP), a rigorous barrier against algorithms exhibiting input stability. In this paper, we focus on the algorithmic tractability of two models: (i) discrepancy minimization, and (ii) the symmetric binary perceptron (SBP), a random constraint satisfaction problem as well as a toy model of a single-layer neural network. Our first focus is on the limits of online algorithms. By establishing and leveraging a novel geometrical barrier, we obtain sharp hardness guarantees against online algorithms for both the SBP and discrepancy minimization. Our results match the best known algorithmic guarantees, up to constant factors. Our second focus is on efficiently finding a constant discrepancy solution, given a random matrix M∈ℝM× n. In a smooth setting, where the entries of M are i.i.d. standard normal, we establish the presence of m-OGP for n=Θ(Mlog M). Consequently, we rule out the class of stable algorithms at this value. These results give the first rigorous evidence towards a conjecture of Altschuler and Niles-Weed~\cite[Conjecture~1]altschuler2021discrepancy. Our methods use the intricate geometry of the solution space to prove tight hardness results for online algorithms. The barrier we establish is a novel variant of the m-OGP. Furthermore, it regards m-tuples of solutions with respect to correlated instances, with growing values of m, m=ω(1). Importantly, our results rule out online algorithms succeeding even with an exponentially small probability.