2 papers
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.DS2025
Quality control in sublinear time: a case study via random graphs
Cassandra Marcussen, Ronitt Rubinfeld, Madhu Sudan
Many algorithms are designed to work well on average over inputs. When running such an algorithm on an arbitrary input, we must ask: Can we trust the algorithm on this input? We id…