Recovering Assignments with One-Sided Noise
The query complexity of recovering a planted assignment from a random constraint-satisfaction instance with one-sided noise is studied, and bounds for nonadaptive algorithms are proved and adaptivity gives a factor $\exp(\Theta(k))$ improvement.