Publications

Spectral graph theory

  • Multi-way spectral partitioning and higher-order Cheeger inequalities [arxiv]

    with S. Oveis Gharan and L. Trevisan.
    Journal of the ACM (2014) and STOC 2012.

  • Cover times, blanket times, and majorizing measures [arxiv]

    with J. Ding and Y. Peres.
    Annals of Math (2013) and STOC 2011.

  • On expanders from the action of GL(2,Z) [pdf]

    Expository note on Margulis-style expanders.

  • Metric uniformization and spectral bounds for graphs [arxiv]

    with J. Kelner, G. Price, and S.-H. Teng.
    Geometric & Functional Analysis (2011).
    Abstract "Higher eigenvalues of graphs" in FOCS 2009.

  • Harmonic maps on amenable groups and a diffusive lower bound for random walks [arxiv]

    with Y. Peres.
    Annals of Probability (2013).

  • Eigenvalue multiplicity and volume growth [pdf]

    with Y. Makarychev.
    Accepted to Journal of Topology and Analysis.

  • Eigenvalue bounds, spectral partitioning, and metrical deformations via flows [arxiv]

    with P. Biswal and S. Rao.
    Journal of the ACM (2010) and FOCS 2008.

  • Eigenvectors of random graphs: Nodal domains [pdf]

    with Y. Dekel and N. Linial.
    Random Strucures & Algorithms (2011) and RANDOM 2007.

Approximation algorithms and hardness of approximation

  • Lower bounds on semidefinite programming relaxations [arxiv]

    with P. Ragahvendra and D. Steurer
    To appear, STOC 2015.

  • On the power of symmetric LP and SDP relaxations [IEEE]

    with P. Raghavendra, D. Steurer, and N. Tan.
    Proceedings of CCC 2014.*

  • Approximate constraint satisfaction requires large LP relaxations [arxiv]

    with S. Chan, P. Raghavendra, and D. Steurer.
    Proceedings of FOCS 2013.

  • A node-capacitated Okamura-Seymour theorem [arxiv]

    with M. Mendel and M. Moharrami.
    Mathematical Programming--Series A and STOC 2013.

  • Lp metrics on the Heisenberg group and the Goemans-Linial conjecture [pdf]

    with A. Naor.
    Proceedings of FOCS 2006.

  • Algorithms on negatively curved spaces [pdf]

    with R. Krauthgamer.
    Proceedings of FOCS 2006.*

  • An improved approximation ratio for the minimum linear arrangement problem [pdf]

    with U. Feige.
    Information Processing Letters (2007).

  • Euclidean distortion and the Sparsest Cut [pdf]

    with S. Arora and A. Naor.
    Journal of the American Mathematical Society (2008) and STOC 2005.

  • Improved approximation algorithms for minimum-weight vertex separators [pdf]

    with U. Feige and M. T. Hajiaghayi.
    SIAM Journal on Computing (2008) and STOC 2005.

  • The black-box complexity of nearest neighbor search [pdf]

    with R. Krauthgamer.
    Theoretical Computer Science (2005) and ICALP 2004.

  • Navigating nets: Simple algorithms for proximity search [pdf]

    with R. Krauthgamer.
    Proceedings of SODA 2004.*

  • Hardness of approximating vertex-connectivity network design problems. [pdf]

    with G. Kortsarz and R. Krauthgamer.
    SIAM Journal on Computing (2004) and APPROX 2002.

Probability, statistics, and stochastic processes

  • Regularization under diffusion and anti-concentration of temperature [arxiv]

    with R. Eldan.

  • A Gaussian upper bound for martingale small-ball probabilities [arxiv]

    with Y. Peres and C. K. Smart.

  • Adversarial hypothesis testing and a quantum Stein's Lemma for restricted measurements [arxiv]

    with F. G. S. L. Brandao, A. W. Harrow, and Y. Peres.
    Proceedings of ITCS 2014.

  • Markov type and threshold embeddings [arxiv]

    with J. Ding and Y. Peres.
    Geometric & Functional Analysis (2013).

  • Cover times, blanket times, and majorizing measures [arxiv]

    with J. Ding and Y. Peres.
    Annals of Math (2013) and STOC 2011.

  • A note on mixing times of planar random walks [arxiv]

    with T. Qin.

  • Harmonic maps on amenable groups and a diffusive lower bound for random walks [arxiv]

    with Y. Peres.
    Annals of Probability (2013).

  • Eigenvectors of random graphs: Nodal domains [pdf]

    with Y. Dekel and N. Linial.
    Random Strucures & Algorithms (2011) and RANDOM 2007.

Metric geometry and applications