ResearchPod Summary
The Learning Parity with Noise (LPN) problem is a cornerstone of modern cryptography, used to build pseudorandom generators, encryption schemes, and zero-knowledge proofs. While efficient algorithms exist for the search and distinguishing variants of LPN, the refutation problem—determining whether a system of linear equations is mostly unsatisfiable—has remained largely unexplored for dense instances. This paper investigates whether subexponential-time algorithms exist for refuting semirandom linear systems and whether these algorithms can be captured by the powerful sum-of-squares (SOS) hierarchy.
The authors develop a subexponential-time refutation algorithm by adapting the bucketing techniques originally introduced by Blum, Kalai, and Wasserman (BKW). The core challenge in refutation is that the standard BKW approach, which is designed to recover a hidden assignment, does not directly provide a certificate of unsatisfiability. The authors overcome this by using a Cauchy-Schwarz-based bucketing procedure that iteratively reduces the bias of the system. They also extend this to a regime requiring only a superlinear number of equations by generating synthetic samples through sparse linear combinations. Finally, they prove a degree-Omega(n) sum-of-squares lower bound to demonstrate that their algorithm is not captured by the SOS hierarchy.
The paper provides the first subexponential-time refutation algorithm for semirandom linear systems, achieving a runtime of 2^O(n/log n) for systems with m = 2^O(n/log n) equations. They also provide a variant that succeeds with only m = n^(1+gamma) equations in 2^O(n/log log n) time. Crucially, the authors prove that for sufficiently dense linear systems, the canonical degree-Omega(n) sum-of-squares relaxation fails to refute the system. This result provides a rare, natural example of a signal recovery problem where efficient algorithms outperform the sum-of-squares hierarchy, suggesting that proving lower bounds for dense LPN requires techniques beyond standard SOS frameworks.
AI-generated third-party summary by ResearchPod. Not official content or an endorsement by the paper authors or affiliated organizations.