Computer Science and Discrete Mathematics (CSDM)

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

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