Showing cs.DSShow 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.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. But when such an algorithm is run on an arbitrary input, the question arises: Can we trust the algorithm on this i…