Seminars Sorted by Series

In this talk, I will describe our construction of the first explicit lossless vertex expanders. These are graphs where every small subset of vertices has about as many neighbors as their sparsity allows. Previously, the strongest known explicit...

Matrix-perturbation bounds quantify how the spectral characteristics of a baseline matrix A change under additive noise E. Classical results, including Weyl’s inequality for eigenvalues and the Davis–Kahan theorem for eigenvectors and eigenspaces...

A conjecture of Komlós states that the discrepancy of any collection of unit vectors is $O(1)$, i.e., for any matrix A with unit columns, there is a vector x with -1,1 entries such that $|Ax|_\infty = O(1)$. The related Beck-Fiala conjecture states...

Over 40 years ago, Karp, Upfal, and Wigderson posed a central open question in parallel computation: how many adaptive rounds are needed to find a basis of a matroid using only independence queries? Their pioneering work gave an upper bound of $O(...

Large language models (LLMs) sometimes generate statements that are plausible but factually incorrect—a phenomenon commonly called "hallucination." We argue that these errors are not mysterious failures of architecture or reasoning, but rather...

In this talk, I will explore the fascinating landscape of assumptions in quantum cryptography—especially, how little we need to assume to build secure quantum protocols. We will cover key cryptographic primitives including quantum encryption...

High-dimensional expanders (HDX) are a generalization of expander graphs which have seen various applications in coding theory, PCPs, pseudorandomness, derandomization, approximate sampling, and beyond. One technique for proving a complex is an HDX...

In this talk, I will discuss the solution to several problems in two closely related settings: set families in 2^[n] with many disjoint pairs, and low-rank matrices with many zero entries.

Highlights include a resolution of an old question of Daykin...