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...
I will present a joint work with Lijie, in which we revise the
hardness vs randomness framework so that it can work in a
non-black-box fashion. That is, we construct derandomization
algorithms that do not rely on classical PRGs, and instead
"extract...
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...
This talk will serve as an introduction to the random algebraic
method. This method has its origins in the following problem:
suppose the binomial random graph comes "close" to having some
property of interest P, but fails to do so because of the...
The degree mantra states that any non-zero univariate polynomial
of degree at most d has at most d roots (counted with
multiplicity). A generalization of this to the multivariate
setting, proved by Dvir-Kopparty-Saraf-Sudan asserts that over
any...
