Strongly Refuting Semirandom Linear Systems in Subexponential Time
In the authors' words
In this paper, we consider the problem of refuting -linear equations with random right-hand sides. Formally, we give a sub-exponential -time randomized algorithm that takes as input an arbitrary matrix and a uniformly random vector , and outputs a witness showing that no assignment satisfies more than a fraction of the equations provided that . The setting above is the semirandom refutation variant of the famous work [BKW03] that gives a -time search algorithm for the learning parity with noise (LPN) problem with equations. Building on the search algorithm of [Lyub05], we also give a -time refutation algorithm that succeeds with only equations, for a small constant . Finally, we prove that our algorithm is not captured by the sum-of-squares hierarchy by proving a degree- sum-of-squares lower bound, showing that "[BKW03]-style" algorithms achieve better runtime than can be done under sum-of-squares. We thus obtain a natural example of a noise-tolerant signal recovery problem that exhibits a nontrivial gap between the performance of efficient algorithms and that of those based on the sum-of-squares hierarchy.
Appeared: Friday, September 25. arXiv. Preprint, not yet peer-reviewed.