Recovery Reductions, Conjectures, and Barriers

Abstract

We introduce and initiate the study of a new model of reductions called the random noise model. In this model, the truth table $T_f$ of the function $f$ is corrupted on a randomly chosen $\hat{I}´$-fraction of instances. A randomized algorithm $\mathcal{A}$ is a $\left(t,\hat{I}´,1-\epsilon \right)$-recovery reduction for $f$ if: 1. With probability $1-\epsilon$ over the choice of $\hat{I}´$-fraction corruptions, given access to the corrupted truth table, the algorithm $\mathcal{A}$ computes $f(\ddot{I}•)$ correctly with probability at least $2/3$ on every input $\ddot{I}•$. 2. The algorithm $\mathcal{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 $\left(poly(n),0.5-1/poly(n),1-e^{-\hat{I}\text{c◯}(poly(n))}\right)$-recovery reductions) for a large function class SLNP${}^S$ containing many of the canonical NP-complete problems - SAT, $k$SAT, $k$CSP, 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 $2^{0.5n}$-time reduction from $k$SAT on $n$ variables; and Parity $k$-Clique a subexponential-time reduction from 3SAT.

37 pages