From the 1 of 5 linked papers with an AI index.
5 papers
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…
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…
Learning and Testing Convex Functions
Renato Ferreira Pinto, Cassandra Marcussen, Elchanan Mossel +1
The paper investigates how to learn and test real-valued convex functions under the Gaussian distribution, providing algorithms with explicit sample‑complexity bounds assuming the…
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…
Finding the root in random nearest neighbor trees
Anna Brandenberger, Cassandra Marcussen, Elchanan Mossel +1
We study the inference of network archaeology in growing random geometric graphs. We consider the root finding problem for a random nearest neighbor tree in dimension $d \in \mathb…