Breaking the Multicommodity Flow Barrier for sqrt(log(n))-Approximations to Sparsest Cut

Positivity improving operators and hypercontractivity

Christer Borell · 1982

Earlier work this paper cites.

A data structure for dynamic trees

Daniel D. Sleator and Robert Endre Tarjan · 1983

Earlier work this paper cites.

λ 1 \lambda_{1} , isoperimetric inequalities for graphs, and superconcentrators

Noga Alon and V. D. Milman · 1985

Earlier work this paper cites.

Fast approximation algorithms for fractional packing and covering problems

Serge A. Plotkin, David B. Shmoys, and Eva Tardos · 1995

Earlier work this paper cites.

Approximating s-t minimum cuts in O ⁡ ( n 2 ) \,{O}(n^{2}) time

András A. Benczúr and David R. Karger · 1996

Earlier work this paper cites.

Beyond the flow decomposition barrier

Andrew V. Goldberg and Satish Rao · 1998

Earlier work this paper cites.

Adaptive game playing using multiplicative weights

Yoav Freund and Robert E. Schapire · 1999

Earlier work this paper cites.

Approximating fractional multicommodity flow independent of the number of commodities

Lisa K. Fleischer · 2000

Cited alongside, same era.

On the optimality of the random hyperplane rounding technique for max cut

Uriel Feige and Gideon Schechtman · 2002

Cited alongside, same era.

Lectures on Discrete Geometry

Jiri Matousek · 2002

Cited alongside, same era.

Database-friendly random projections: Johnson-lindenstrauss with binary coins

Dimitris Achlioptas · 2003

Cited alongside, same era.

Concentration inequalities

Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet · 2003

Cited alongside, same era.

Expander flows, geometric embeddings and graph partitioning

Sanjeev Arora, Satish Rao, and Umesh Vazirani · 2004

Cited alongside, same era.

Euclidean distortion and the sparsest cut

Sanjeev Arora, James R. Lee, and Assaf Naor · 2005

Later among the works it cites.

On distance scales, embeddings, and efficient relaxations of the cut cone

James R. Lee · 2005

Later among the works it cites.

Graph partitioning using single commodity flows

Rohit Khandekar, Satish Rao, and Umesh Vazirani · 2006

Later among the works it cites.

Non-interactive correlation distillation, inhomogeneous markov chains, and the reverse bonami-beckner inequality

Elchanan Mossel, Oded Regev, Jeffrey E. Steif, and Benny Sudakov · 2006

Later among the works it cites.

A combinatorial, primal-dual approach to semidefinite programs

Sanjeev Arora and Satyen Kale · 2007

Later among the works it cites.

On partitioning graphs via single commodity flows

Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani, and Nisheeth K. Vishnoi · 2008