- Randomized algortihms & probabilistic analysis
- Hypercontractivity and its applications [Punya Biswal]
- Majorizing measures and Gaussian processes [rough draft]
- Planar multi-flows,
L
_{1}embeddings, and differentiation - Bloomington summer school on Analysis and geometry in the theory of computation
- Selected tcsmath posts

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

**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.**L**[pdf]_{p}metrics on the Heisenberg group and the Goemans-Linial conjecturewith 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.

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

- A node-capacitated Okamura-Seymour theorem
[arxiv]
with M. Mendel and M. Moharrami.

Mathematical Programming--Series A and STOC 2013. - Markov type and threshold embeddings
[arxiv]
with J. Ding and Y. Peres.

Geometric & Functional Analysis (2013). **A lower bound on dimension reduction for trees in L**[arxiv]_{1}with M. Moharrami.

**On the 2-sum embedding conjecture**[ACM DL]with D. Poore.

Proceedings of SoCG 2013.***On the Hausdorff dimension of ultrametric subsets in R**[arxiv]^{n}with M. Mendel and M. Moharrami.

Fundamenta Mathematicae (2012).**Dimension reduction for finite trees in L**[arxiv]_{1}with A. de Mesmay and M. Moharrami.

Discrete & Computational Geometry (2013) and SODA 2012.**Near-optimal distortion bounds for embedding doubling spaces into L**[pdf]_{1}with A. Sidiropoulos.

Proceedings of STOC 2011.***Bilipschitz snowflakes and metrics of negative type**[ACM DL]with M. Moharrami. Proceedings of STOC 2010.*

**Genus and the geometry of the cut graph**with A. Sidiropoulos.

Proceedings of SODA 2010.***On the optimality of gluing over scales**[arxiv]with A. Jaffe and M. Moharrami.

Discrete & Computational Geometry (2011) and APPROX 2009.**Sparsest Cut on quotiens of the hypercube**with A. Kolla.

**Randomly removing g handles at once**[arxiv]with G. Borradaile and A. Sidiropoulos.

Computational Geometry, Theory and Applications (2010) and SoCG 2009.**Pathwidth, trees, and random embeddings**[arxiv]with A. Sidiropoulos.

Combinatorica (2013).**On the geometry of graphs with a forbidden minor**[pdf]with A. Sidiropoulos.

Proceedings of STOC 2009.***Euclidean sections of L**[pdf]_{1}^{n}with sublinear randomness and error-correction over the realswith V. Guruswami and A. Wigderson.

Proceedings of RANDOM 2008.**Local moves and lossy invariants in planar graph embeddings**[pdf]with A. Chakrabarti, A. Jaffe, and J. Vincent.

Proceedings of FOCS 2008.***Almost Euclidean subspaces of L**[pdf]_{1}^{n}via expander codeswith V. Guruswami and A. Razborov.

Combinatorica (2010) and SODA 2008.**Coarse differentiation and planar multi-flows**[pdf]with P. Raghavendra.

Discrete & Computational Geometry (2010) and APPROX 2007.**Vertex cuts, random walks, and dimension reduction in series-parallel graphs**[pdf]with B. Brinkman and A. Karagiozova.

Proceedings of STOC 2007.***Trees and Markov convexity**[arxiv]with A. Naor and Y. Peres.

Geometric and Functional Analysis (2009) and SODA 2006.- L
_{p}metrics on the Heisenberg group and the Goemans-Linial conjecture [pdf]with A. Naor.

Proceedings of FOCS 2006. **Volume distortion for subsets of Euclidean spaces**[pdf]Discrete & Computational Geometry (2009) and SoCG 2006.

**Frechet embeddings of negative type metrics**[pdf]with S. Arora and A. Naor.

Discrete & Computational Geometry (2007).- Euclidean distortion and the Sparsest Cut
[pdf]
with S. Arora and A. Naor.

Journal of the American Mathematical Society (2008) and STOC 2005. **Distance scales, embeddings, and metrics of negative type**[pdf]Proceedings version in SODA 2005.

**Measured descent: A new embedding method for finite metrics**[pdf]

with R. Krauthgamer, M. Mendel, and A. Naor.

Geometric and Functional Analysis (2005) and FOCS 2004.**Absolute Lipschitz extendability**with A. Naor.

Comptes Rendus de l'Acadèmie des Sciences - Series I - Mathematics (2004).**Extending Lipschitz functions via random metric partitions**[pdf]with A. Naor.

Inventiones Mathematicae (2005).**Metric structures in L**[pdf]_{1}: Dimension, snowflakes, and average distortionwith M. Mendel and A. Naor.

European Journal of Combinatorics (2005).**Embedding the diamond graph in L**[pdf]_{p}and dimension reduction in L_{1}with A. Naor.

Geometric and Functional Analysis (2004).**Bounded geometries, fractals, and low-distortion embeddings**[pdf]with A. Gupta and R. Krauthgamer.

Proceedings of FOCS 2003.***The intrinsic dimensionality of graphs**[pdf]with R. Krauthgamer.

Combinatorica (2007) and STOC 2003.