2021-2022 Seminars

The absorption method is a very simple yet surprisingly powerful idea coming from extremal combinatorics which allows one to convert asymptotic results into exact ones. It has produced a remarkable number of success stories in recent years with...

Proving a 2009 conjecture of Itai Benjamini, we show:  For any C, there is a > 0 such that for any simple random walk on an n-vertex graph G, the probability that the first Cn steps of the walk hit every vertex of G is at most exp[-an].  A first...

Two recent and seemingly-unrelated techniques for proving mixing bounds for Markov chains are:

(i) the framework of Spectral Independence, introduced by Anari, Liu and Oveis Gharan, and its numerous extensions, which have given rise to several...

Over the last three decades, the online bipartite matching (OBM) problem has emerged as a central problem in the area of Online Algorithms. Perhaps even more important is its role in the area of Matching-Based Market Design.  The resurgence of this...

Two recent and seemingly-unrelated techniques for proving mixing bounds for Markov chains are:

(i) the framework of Spectral Independence, introduced by Anari, Liu and Oveis Gharan, and its numerous extensions, which have given rise to several...

As machine learning is widely deployed, it is increasingly important to ensure that predictors will perform well not only on average (across the entire population), but also on specific socially salient subgroups. In this talk, I will present...

In recent years, a new “fine-grained” theory of computational hardness has been developed, based on “fine-grained reductions” that focus on exact running times for problems. 

We follow the fashion of NP-hardness in a more delicate manner. We...

Understanding the complexity of the Minimum Circuit Size Problem (MCSP) is a longstanding mystery in theoretical computer science. Despite being a natural problem about circuits (given a Boolean function's truth table, determine the size of the...

This is the third and final talk in the joint series with Lijie Chen. The talk will NOT rely on the technical contents from the two previous talks.

I will present a joint work with Lijie, in which we revise the hardness vs randomness framework so...

I'll present a new algorithm to refute, that is, efficiently find certificates of unsatisfiability, for smoothed instances of k-SAT and other CSPs. Smoothed instances are produced by starting with a worst-case instance and flipping each literal in...