Computer Science Colloquium Series - Student Session

There will be two talks for the 10/22/26 Colloquium: Title: Quality Control Algorithms for Pattern Counting Speaker: Cassandra Marcussen, graduate student at Harvard SEAS Abstract: When can we trust an algorithm that works well on random inputs on 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 permutation patterns (the relative order of entries in a sequence) and predictions from an i.i.d. model. For patterns of length k, estimating their frequency on arbitrary inputs requires exponentially many queries. We show that quality control requires only polynomially many queries. Based on joint work with Ronitt Rubinfeld and Madhu Sudan. Speaker Bio: Cassandra Marcussen is a fifth-year Ph.D. student in computer science at Harvard University, advised by Madhu Sudan. Her research focuses on sublinear and local algorithms, average-case complexity, and quasirandomness. She is particularly interested in how computation can remain reliable when only limited information about the input is available. Her research is supported by an NDSEG Fellowship. ------------- Title: The Power of Adaptivity in Quantum Learning Speaker: Weiyuan Gong, graduate student at Harvard SEAS Abstract: Adaptivity is one of the most powerful ideas in machine learning and AI: what a learner has learned so far should decide what data it collects next. In active learning, binary search finds a threshold with exponentially fewer labels than random sampling. Yet in quantum learning, where every measurement disturbs the state it probes, adaptivity has been proven to offer little or no advantage for many basic tasks. In this talk, I will show that adaptivity can nonetheless bring dramatic improvements to learning from quantum data. For stabilizer states, an essential subclass of quantum states, adaptive single-copy measurements need quadratically fewer copies than non-adaptive ones. For predicting many properties of a multi-qubit system, first learning where to look saves exponentially many copies over comparable non-adaptive strategies. For Gaussian states of light, adaptivity cuts the number of copies needed from linear to doubly logarithmic in the energy, which we prove is optimal for any strategy using Gaussian measurements. In short, what you learn should decide what you measure in the quantum world, with savings ranging from quadratic to doubly exponential. Speaker Bio: Weiyuan Gong is a PhD student at Harvard SEAS, advised by Sitan Chen. He works on quantum learning theory, quantum algorithms, and quantum complexity theory.