Recovery Reductions, Conjectures, and Barriers

We introduce and initiate the study of a new model of reductions called the random noise model. In this model, the truth table Tf of the function f is corrupted on a randomly chosen $δ$-fraction of instances. A randomized algorithm A is a (t, δ, 1-ε)-recovery reduction for f if: 1. With probability 1-ε over the choice of $δ$-fraction corruptions, given access to the corrupted truth table, the algorithm A computes $f(ϕ)$ correctly with probability at least $2/3$ on every input $ϕ$. 2. The algorithm A runs in time $O(t)$. This model, a natural relaxation of average-case complexity, has practical motivations and is mathematically interesting. Pointing towards this, we show the existence of robust deterministic polynomial-time recovery reductions with optimal parameters up to polynomial factors (that is, deterministic ( poly(n), 0.5 - 1/poly(n), 1-e-Ω(poly(n)) )-recovery reductions) for a large function class SLNPS containing many of the canonical NP-complete problems - SAT, kSAT, kCSP, CLIQUE and more. As a corollary, we obtain that the barrier of Bogdanov and Trevisan (2006) for non-adaptive worst-case to average-case reductions does not apply to our mild non-adaptive relaxation. Furthermore, we establish recovery reductions with optimal parameters for Orthogonal Vectors and Parity k-Clique problems. These problems exhibit structural similarities to NP-complete problems, with Orthogonal Vectors admitting a 20.5n-time reduction from kSAT on n variables; and Parity k-Clique a subexponential-time reduction from 3SAT.