Abstract
In this paper, we initiate the study of the algorithmic problem of certifying lower bounds on the discrepancy of random matrices: given an input matrix A ∈ ℝ^{m × n}, output a value that is a lower bound on disc(A) = min_{x ∈ {± 1}ⁿ} ‖Ax‖_∞ for every A, but is close to the typical value of disc(A) with high probability over the choice of a random A. This problem is important because of its connections to conjecturallyhard averagecase problems such as negativelyspiked PCA [Afonso S. Bandeira et al., 2020], the numberbalancing problem [Gamarnik and Kızıldağ, 2021] and refuting random constraint satisfaction problems [Prasad Raghavendra et al., 2017]. We give the first polynomialtime algorithms with nontrivial guarantees for two main settings. First, when the entries of A are i.i.d. standard Gaussians, it is known that disc(A) = Θ (√n2^{n/m}) with high probability [Karthekeyan Chandrasekaran and Santosh S. Vempala, 2014; Aubin et al., 2019; Paxton Turner et al., 2020] and that superconstant levels of the SumofSquares SDP hierarchy fail to certify anything better than disc(A) ≥ 0 when m < n  o(n) [Mrinalkanti Ghosh et al., 2020]. In contrast, our algorithm certifies that disc(A) ≥ exp(O(n²/m)) with high probability. As an application, this formally refutes a conjecture of Bandeira, Kunisky, and Wein [Afonso S. Bandeira et al., 2020] on the computational hardness of the detection problem in the negativelyspiked Wishart model. Second, we consider the integer partitioning problem: given n uniformly random bbit integers a₁, …, a_n, certify the nonexistence of a perfect partition, i.e. certify that disc(A) ≥ 1 for A = (a₁, …, a_n). Under the scaling b = α n, it is known that the probability of the existence of a perfect partition undergoes a phase transition from 1 to 0 at α = 1 [Christian Borgs et al., 2001]; our algorithm certifies the nonexistence of perfect partitions for some α = O(n). We also give efficient nondeterministic algorithms with significantly improved guarantees, raising the possibility that the landscape of these certification problems closely resembles that of e.g. the problem of refuting random 3SAT formulas in the unsatisfiable regime. Our algorithms involve a reduction to the Shortest Vector Problem and employ the LenstraLenstraLovász algorithm.
BibTeX  Entry
@InProceedings{venkat:LIPIcs.ITCS.2023.98,
author = {Venkat, Prayaag},
title = {{Efficient Algorithms for Certifying Lower Bounds on the Discrepancy of Random Matrices}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {98:198:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772631},
ISSN = {18688969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17601},
URN = {urn:nbn:de:0030drops176015},
doi = {10.4230/LIPIcs.ITCS.2023.98},
annote = {Keywords: Averagecase discrepancy theory, lattices, shortest vector problem}
}
Keywords: 

Averagecase discrepancy theory, lattices, shortest vector problem 
Collection: 

14th Innovations in Theoretical Computer Science Conference (ITCS 2023) 
Issue Date: 

2023 
Date of publication: 

01.02.2023 