Approximation Algorithms

Approximate Counting / Sampling

Lower Bounds

D. Abdolazimi, K. Lindberg, S. Oveis Gharan, On Optimization and Counting of Non-Broken Bases of Matroids, submitted, 2023.

A. Abdolazimi, S. Oveis Gharan, An Improved Trickle-Down Theorem for Partite Complexes, CCC 2023.

P. Beame, S. Oveis Gharan, X. Yang, Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions, COLT 2018.

Spectral Graph Theory

Stochastic/Online/Distributed Algorithms