Approximation Algorithms


Approximate Counting / Sampling


Lower Bounds

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

Spectral Graph Theory


Stochastic/Online Algorithms