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 2^0. 5n-time reduction from kSAT on n variables; and Parity k-Clique a subexponential-time reduction from 3SAT.
Nareddy et al. (Wed,) studied this question.