Proving a 2009 conjecture of Itai Benjamini, we show: For
any C, there is a greater than 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]. ...
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...
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...
