Showing 2026Show all
2 papers · 1 filter
cs.DS2026
Quality Control Algorithms for Pattern Counting
Cassandra Marcussen, Ronitt Rubinfeld, Madhu Sudan
In recent work, Marcussen, Rubinfeld, and Sudan introduced the notion of quality control problems, which aim to capture the task of determining if a given input is truly random. Fo…
cs.DS2026
Recovering Assignments with One-Sided Noise
Cassandra Marcussen, Elchanan Mossel, Colin Sandon
We study the query complexity of recovering a planted assignment from a random constraint-satisfaction instance with one-sided noise. We consider the following 1-CNF recovery probl…