2023-2024 Seminars

A recent line of work has shown a surprising connection between multicalibration, a multi-group fairness notion, and omniprediction, a learning paradigm that provides simultaneous loss minimization guarantees for a large family of loss functions...

Coboundary expansion and cosystolic expansion are generalizations of edge expansion to hypergraphs. In this talk, we will first explain how the generalizations work. Next we will motivate the study of such hypergraphs by looking at their...

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits. Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested approaching this problem by proving that depth...

A weighted pseudorandom generator (WPRG) is a generalization of a pseudorandom generator (PRG) in which, roughly speaking, probabilities are replaced with weights that are permitted to be positive or negative. In this talk, we present new explicit...

Is randomness ever necessary for space-efficient computation? It is commonly conjectured that L = BPL, meaning that halting decision algorithms can always be derandomized without increasing their space complexity by more than a constant factor. In...

Consider a function on $R^n$ that can be written as a sum of functions $f = f_1$ + $f_2$ + ... + $f_m$, for $m >> n$.

The question of approximating f by a reweighted sum using only a small number of summands has many applications in CS theory...

Strong spatial mixing (SSM) is an important and widely studied quantitative notion of "correlation decay" for a variety of natural distributions arising in statistical physics, probability theory, and theoretical computer science. One of the most...

Explicit constructions of "random-like" objects play an important role in complexity theory and pseudorandomness. For many important objects such as prime numbers and rigid matrices, it remains elusive to find fast deterministic algorithms for...

While the notion of spectral gap is a fundamental and very useful feature of reversible Markov chains, there is no standard analogue of this notion for nonreversible chains. In this talk, I will present a simple proposal for spectral gap of...

High dimensional expanders are an exciting generalization of expander graphs to hypergraphs and other set systems.  Loosely speaking, high dimensional expanders are sparse approximation to the complete hypergraph.  In this talk, we’ll give a gentle...