PaperlayerView exact revision on arXiv

Source-linked AI summary

Strongly Refuting Semirandom Linear Systems in Subexponential Time

Pravesh K. Kothari, Andrew D. Lin, Peter Manohar

arXiv:2609.30052v1cs.DS

TL;DR

The paper asks whether refutation analogues of exist and whether there is evidence those algorithms may be optimal. It gives semirandom refutation algorithms and proves a degree-Ω(n) sum-of-squares lower bound, showing the algorithms are not captured by that hierarchy.

  • Problem

    The paper asks whether refutation analogues of exist and whether evidence can support their optimality, when no nontrivial algorithm for LPN refutation was known.

    Source: §1 · pp. 3–4

  • Method

    It gives semirandom refutation algorithms for arbitrary equation matrices, combining equations into synthetic systems and iteratively zeroing left-hand-side blocks to bound the final system's value.

    Source: §1 · p. 4, §3.1 · p. 12

  • Results

    Ω(n)-degree sum-of-squares lower bounds show the refutation algorithms are not captured by the hierarchy; their runtime and sample-complexity guarantees match [BKW03] and search algorithms.

    Source: §1 · p. 4, §1.1 · p. 5

  • Takeaways & Limitations

    Since sum-of-squares degree roughly corresponds to runtime, the lower bound is typically interpreted as a 2^Ω(n)-time lower bound, which these algorithms violate.

    Source: §1 · p. 4

    The stated condition on S alone is not a certificate for the original system, since systems can satisfy it while having val(A,b) ≥ 1.

    Source: §2.2 · p. 7

Abstract

from arXiv · show

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}+\epsilon$ 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 + \gamma}$ equations, for a small constant $\gamma$. Finally, we prove that our algorithm is not captured by the sum-of-squares hierarchy by proving a degree-$\Omega(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.

1 Introduction

The paper introduces refutation algorithms for random and semirandom LPN systems, where refutation means certifying that no assignment satisfies more than a 1/2+ε fraction of equations. It also gives an SOS lower bound showing a gap between these algorithms and the hierarchy.

1 Introduction

  • Refutation asks for a certificate that no assignment satisfies more than a 1/2+ε fraction of equations, unlike search, which seeks the hidden assignment.The related algorithm handles distinguishing and search with m=2^O(n/log n) equations; reduces the sample requirement to n^(1+γ) at higher runtime in the random setting.Source: §1 · p. 3
  • The paper addresses a gap: no nontrivial LPN refutation algorithm was known, despite extensive study of sparse LPN refutation and lower bounds.The motivating questions ask whether refutation analogues of and exist and whether there is evidence they may be optimal.Source: §1 · pp. 3–4

1.1 Our results

  • The paper gives the first subexponential-time refutation algorithms for random and semirandom linear systems, with guarantees matching the search algorithms [BKW03] and.The semirandom guarantee holds for every choice of A, unlike search in its low-sample setting.Source: §1 · p. 4
  • An Ω(n)-degree sum-of-squares lower bound shows the refutation algorithms are not captured by the hierarchy, whose degree roughly corresponds to runtime.The lower-bound distribution uses rows with expected support size n/log n, rather than the standard uniform-A LPN distribution.Source: §1 · p. 4, §1.1 · p. 5
  • With m=n^(1+γ) equations, the paper gives a semirandom refutation algorithm running in 2^Θ(n/log log n) time.This increases runtime while reducing the equation requirement to a superlinear number.Source: §1.1 · p. 5
  • The SOS lower bound concerns a distribution different from standard LPN because encoding dense equations as real polynomial constraints can require degree about n/2.The paper uses equations whose supports have expected size n/log n; the algorithm's semirandom guarantee applies to this input distribution as well.Source: §1.1 · p. 5

2 Proof Overview

The overview adapts BKW-style vector combining to refutation by tracking how bias survives transformations and controlling the growth of generated equations. It also extends refutation to the sparse-sample regime and gives a sum-of-squares lower-bound strategy.

2.1 The search algorithm of [BKW03]

  • BKW’s search strategy finds sparse combinations summing to a basis vector, allowing the corresponding right-hand sides to estimate a hidden coordinate despite noise.The coordinate estimate’s correlation decreases exponentially with the combination’s size, motivating sparse combinations.Source: §2.1 · p. 6

2.2 Refutation via BKW-style bucketing: challenges and our approach

  • A low fraction of zero-sum combinations is not itself a refutation certificate, because the transformed system’s value has no obvious relation to the original system’s value.Some systems satisfy the zero-sum condition while still having value at least 1/2 + ε.Source: §2.2 · p. 7
  • Equal-size buckets and pairwise equation combining preserve a squared-scale bias: bias(A, b) ≥ ε implies bias(A′, b′) ≥ Ω(ε^2).The argument uses Cauchy–Schwarz.Source: §2.2 · p. 7
  • Repeated block transformations preserve a lower bound on bias while eventually producing zero left-hand sides, whose right-hand-side imbalance certifies refutation.The overview states bias(A′′, b′′)^(1/2^r) ≥ bias(A, b); when all transformed rows are zero, the right-hand-side imbalance certifies the original instance.Source: §2.2 · p. 7
  • A naive all-pairs procedure grows the equation count too quickly, while sub-bucketing limits each round’s growth and keeps the runtime at 2^O(n/log n).The naive growth can exceed 2^O(n), whereas sub-buckets limit the per-round factor to 2^O(n/log^2 n).Source: §2.2 · pp. 7–8
  • A 1/2 + O(ε) bound holds on all but an O(ε)-fraction of parts in the sparse-sample extension.The construction uses deterministic synthetic-sample generation, then partitions the equations so most parts have no trivial even covers and can be refuted separately.Source: §2.2 · p. 8

2.3 Sum of squares lower bounds for linear systems

  • A degree-Ω(n) pseudoexpectation can treat the system as satisfiable; the proof strategy rules out short even covers and forces resolution refutations to reach degree Ω(n).It also establishes an interval of combination sizes for which every combination has Hamming weight Ω(n).Source: §2.3 · p. 9

3 Refuting Semirandom Linear Systems

Section 3 develops algorithms for refuting semirandom linear systems across different sample-size and runtime regimes, using REFUTE to upper-bound system value. It describes how REFUTE constructs that bound and establishes supporting bounds for its iterative construction and q-uniform tests, including bias, premature termination, satisfaction rates, and short even covers after random partitioning.

3 Refuting Semirandom Linear Systems

  • For m ≥ 2^{3n/log n}, a poly(m)-time algorithm outputs V ≤ 1/2 + ε with high probability on semirandom systems.Theorem 1.2 gives this guarantee for the stated range of ε.Source: §3 · p. 9
  • For m = n^{1+γ}, an algorithm runs in 2^{Θ(n/log log n)} time and outputs a refutation bound for semirandom systems.Theorem 1.3 specifies a range of ε for its guarantee.Source: §3 · p. 9
  • REFUTE runs in r·poly(M·2^{n/r}) time and returns B such that val(A, b, T) ≤ 1/2 + B.These are the runtime and value guarantees of Lemma 3.2.Source: §3 · p. 10

3.1 Proof of Lemma 3.2

  • REFUTE repeatedly pairs equations sharing a block of n/r coordinates, zeroes out coordinate blocks over r steps, and uses the resulting induced system to upper-bound the original system’s value.The algorithm tracks right-hand sides and the original equations contributing to each combined equation.Source: §3.1 · p. 12
  • With enough input sets and no even covers of length at most 2r+1, REFUTE’s premature output of 1/2 is unlikely; on semirandom systems, B is small with high probability if it does not terminate prematurely.The semirandom guarantee applies when M meets the stated threshold and ε exceeds the stated lower bound.Source: §3.1 · p. 13
  • Repeated bias-squaring bounds yield val(A, b, T) ≤ 1/2 + B for the constructed final set.The proof bounds final bias by repeatedly applying the preceding bias-squaring lemma.Source: §3.1 · p. 14
  • At level k, a fixed original equation occurs in at most 2^(nk/r^2) derivations, a count used to control collisions during the construction.The bound follows by induction on k.Source: §3.1 · p. 15
  • With the stated lower bounds on M, Algorithm 3 avoids premature termination with probability at least 1 - 25·2^(-n/(6r)) when T has no even cover of length at most 2r + 1.The bound combines the probabilities for avoiding termination at Items 3e and 4.Source: §3.1 · pp. 15–17

3.2 Proofs of Lemmas 3.3 and 3.4

  • With m = n^(1+γ), random partitioning leaves at most a 2^(-8n/(γ log n)) fraction of parts containing an even cover of size at most log n, with probability 1 - 2^(-n/(γ log n)).Each part has 2^(3n/log log n) edges, and q = 6n^γ log n log log n.Source: §3.2 · p. 18

4 Sum-of-Squares Lower Bounds for Refuting Linear Systems

The section establishes a degree-Ω(n) sum-of-squares lower bound for refuting specified random sparse linear systems. Its proof uses large-width resolution refutations to obtain pseudoexpectations, separating the hierarchy from the paper’s faster algorithm.

4 Sum-of-Squares Lower Bounds for Refuting Linear Systems

  • Theorem 1.2 runs in 2^O(n/log n) time, while sum-of-squares fails to refute these systems within 2^Ω(n) time.The lower bound follows from a degree-Ω(n) pseudoexpectation for the specified random sparse systems.Source: §4 · p. 19
  • A resolution refutation is built by multiplying polynomial equations and their signs until it derives (1, −1) or (−1, 1); its width is the maximum multilinear degree.The definition reduces powers using x_i^2 = 1.Source: §4 · p. 19
  • Fact 4.4 turns the absence of narrow resolution refutations into a degree-w/2 pseudoexpectation when each equation polynomial has degree at most w/2.The proof shows every resolution refutation has width Ω(n), yielding the sum-of-squares lower bound.Source: §4 · pp. 19, 21
  • The width argument uses that short subsets of the random vectors have no zero sum, while sums of specified intermediate-size subsets have Hamming weight Ω(n).The lemma establishes these properties with high probability; the proof uses them to force a large-degree monomial in every refutation.Source: §4 · pp. 19, 21
Loading 2609.30052v1…