6 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
We consider the problems of \emph{learning} and \emph{testing} real-valued convex functions over Gaussian space. Despite the extensive study of function convexity across mathematic…
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…
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…
Errors are Robustly Tamed in Cumulative Knowledge Processes
Anna Brandenberger, Cassandra Marcussen, Elchanan Mossel +1
We study processes of societal knowledge accumulation, where the validity of a new unit of knowledge depends both on the correctness of its derivation and on the validity of the un…