Efficient algorithms for certifying lower bounds on the discrepancy of random matrices
summary
Proves a deterministic polynomial-time algorithm that with high probability certifies discrepancy ≥ exp(−n^2/m) for an m×n Gaussian matrix, and a nondeterministic polynomial-time verifier that certifies the stronger bound exp(−n log n / m). Key tools are an algorithmic John's theorem, a reduction to the Shortest Vector Problem on lattices plus SVP approximation, and a lattice-based certificate that outperforms semidefinite programs (SDPs fail to certify any nontrivial lower bound). Also gives a corollary for detection in the negatively-spiked Wishart model.
AI-written summary · about