Seminars Sorted by Series

In both computer science and economics, efficiency is a cherished property. The field of algorithms is almost solely focused on their efficiency. The goal of AI research is to increase efficiency by reducing human labor.  In economics, the main...

Private Information Retrieval (PIR) is a method for a user to interact with t non-colluding servers and read some entry of a database of size n without revealing to the servers anything about which entry of the database was read. After a long line...

Although current large language models are complex, the most basic specifications of the underlying language generation problem itself are simple to state: given a finite set of training samples from an unknown language, produce valid new strings...

In theoretical computer science, an increasingly important role is being played by sparse high-dimensional expanders (HDXs), of which we know two main constructions: "building" HDXs [Ballantine'00, ...] and "coset complex" HDXs [Kaufman--Oppenheim...

This talk will be about two related results, one in complexity theory and one in learning.

On the learning side, we investigate the sample complexity of smooth boosters - These are boosting algorithms that do not place too much weight on any given...

I will describe a recent extension of the classical PAC (Probably Approximately Correct) learning framework [Vapnik and Chervonenkis, 1970s; Valiant, 1980s]. This extension makes it possible to model a wide range of common and practical data...

Abstract: A linear extension of $P$ is a linear ordering compatible with the poset relations. Let $p(x< y), p(y < x))$ and $\delta(P)$ be the maximum value of $\delta(x, y)$ over all $x, y$ in $P$. The following two conjectures about $\delta(P)$ are both well-known:

1. (The "1/3-2/3 Conjecture") $\delta(P) \geq \frac{1}{3}$ whenever $P$ is not a chain.
2. (The "Kahn-Saks Conjecture") $\delta(P) \to \frac{1}{2}$ as $w(P) \to \infty$ (where $w(P)$ is the maximum size of an antichain in $P$).

While still far from either of these, we prove a number of conditions for $\delta(P) \to \frac{1}{2}$ and $\delta(P) \geq \frac{1}{e} - o(1)$, using a mix of geometric and probabilistic techniques. Joint with Jeff Kahn.

What is the cost of a task if we have to perform it many times? Can we achieve economies of scale? Such "direct-sum problems" play a central role in many areas of mathematics, physics and computer science. Protagonistic problems of this kind are...

In this work, we develop a new method for proving lower bounds for static data structures in the classical cellprobe model of Yao. Our methods give the strongest known lower bounds for any explicit problem in this model (quadratically stronger for...

In 1984 W. B. Johnson and J. Lindenstrauss showed that a random projection of an arbitrary point set S into low-dimensional space is approximately distance-preserving, as long as S is of size at most exponential in the target dimension. The...

In the NISQ era, where noise limits device coherence times, we are fundamentally constrained to shallow quantum computation. This talk will explore the power, limitations, and learnability of the $QAC^0$ circuit class--i.e. the family of constant...

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...