Please note: This seminar will take place in DC 1304 and online.
Cassandra Marcussen, PhD student
Harvard John A. Paulson School of Engineering and Applied Sciences, Harvard University
When can we trust predictions based on random inputs when working with real-world data? I will introduce quality control algorithms, which accept random inputs while rejecting inputs for which a prediction is substantially wrong, with high probability. I will focus on checking whether permutation pattern frequencies in a given sequence are close to those predicted for i.i.d. data. A permutation pattern describes the relative order of entries in a subsequence. For patterns of length k, estimating their frequency on arbitrary inputs requires exponentially many queries. I will show that quality control for these predictions requires only polynomially many queries.
Based on joint work with Ronitt Rubinfeld and Madhu Sudan.
To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.