Efficient algorithms for certifying lower bounds on the discrepancy of random matrices
share
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 𝖽𝗂𝗌𝖼(A) = min_x ∈{± 1}^n ||Ax||_∞ for every A, but is close to the typical value of 𝖽𝗂𝗌𝖼(A) with high probability over the choice of a random A. This problem is important because of its connections to conjecturally-hard average-case problems such as negatively-spiked PCA, the number-balancing problem and refuting random constraint satisfaction problems. We give the first polynomial-time algorithms with non-trivial guarantees for two main settings. First, when the entries of A are i.i.d. standard Gaussians, it is known that 𝖽𝗂𝗌𝖼 (A) = Θ (√(n)2^-n/m) with high probability. Our algorithm certifies that 𝖽𝗂𝗌𝖼(A) ≥exp(- O(n^2/m)) with high probability. As an application, this formally refutes a conjecture of Bandeira, Kunisky, and Wein on the computational hardness of the detection problem in the negatively-spiked Wishart model. Second, we consider the integer partitioning problem: given n uniformly random b-bit integers a_1, …, a_n, certify the non-existence of a perfect partition, i.e. certify that 𝖽𝗂𝗌𝖼 (A) ≥ 1 for A = (a_1, …, 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; our algorithm certifies the non-existence of perfect partitions for some α = O(n). We also give efficient non-deterministic algorithms with significantly improved guarantees. Our algorithms involve a reduction to the Shortest Vector Problem.
READ FULL TEXT