Algorithms refute semirandom linear equations faster than known methods
Strongly Refuting Semirandom Linear Systems in Subexponential Time
Data Structures and Algorithms
Summary
The paper tackles the problem of proving that certain systems of equations with random components cannot be mostly satisfied by any assignment. The authors develop new algorithms that work faster than previously known ones for finding such proofs under specific conditions. They also show that a common powerful mathematical technique, the sum-of-squares method, cannot match their algorithm’s performance in this task. This provides a clearer understanding of the limits of existing tools for solving noisy linear problems.
What this means in practice
- •For cryptography developers: Assess security guarantees of cryptographic schemes based on learning parity with noise assumptions by using faster refutation algorithms for semirandom linear systems.
- •For error correction engineers: Improve understanding of noise-tolerant decoding methods by leveraging new subexponential algorithms for verifying limits on satisfiability in noisy linear systems.
A theory result. No direct application yet.
Authors
Pravesh K. Kothari, Andrew D. Lin, Peter Manohar
Abstract
In this paper, we consider the problem of refuting $\mathbb{F}_2$-linear equations with random right-hand sides. Formally, we give a sub-exponential $2^{O(n/\log n)}$-time randomized algorithm that takes as input an arbitrary $m \times n$ matrix $A$ and a uniformly random vector $b \in \mathbb{F}_2^m$, and outputs a witness showing that no assignment satisfies more than a $\frac{1}{2}+ε$ fraction of the equations provided that $m \geq 2^{O(n/\log n)}$. The setting above is the semirandom refutation variant of the famous work [BKW03] that gives a $2^{O(n/\log n)}$-time search algorithm for the learning parity with noise (LPN) problem with $m \geq 2^{O(n/\log n)}$ equations. Building on the search algorithm of [Lyub05], we also give a $2^{O(n/\log \log n)}$-time refutation algorithm that succeeds with only $m \geq n^{1 + γ}$ equations, for a small constant $γ$. Finally, we prove that our algorithm is not captured by the sum-of-squares hierarchy by proving a degree-$Ω(n)$ 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.