Theory of Computation

Formulas Resilient to Short-Circuit Errors

Y.T. Kalai, A. Lewko, A. Rao, 2012.

Multi-way spectral partitioning and higher-order Cheeger inequalities

J.R. Lee, S. OveisGharan, L. TrevisanSTOC, 2012.

Cover times, blanket times, and majorizing measures

J.R. Lee, J. Ding, Y. PeresSTOC, 2011.

On the value of multiple read/write streams for approximating frequency moments

P. Beame, T. HuynhACM Transactions on Computation Theory, 2011.

Prior-independent Multi-parameter Mechanism Design

N. Devanur, J. Hartline, A. Karlin, T. Nguyen, 2011.

How to Compress Interactive Communication

B. Barak, M. Braverman, X. Chen, A. RaoSTOC, 2010.

Metric Uniformization and Spectral Bounds for Graphs

J.A. Kelner, J.R. Lee, G.N. Price, S.H. TengFOCS, 2009.

Quantum algorithm for solving linear systems of equations

A.W. Harrow, A. Hassidim, S. LloydPhysical Review Letters 15:103, 2009.

Quantum Reverse Shannon Theorem

C.H. Bennett, I. Devetak, A.W. Harrow, P.W. Shor, A. Winter, 2009.