James R. Lee

Discret. Comput. Geom., March, 2024

2023

Sparsifying generalized linear models.

[BibT_eX]

[DOI]

CoRR, 2023

Spectral Hypergraph Sparsification via Chaining.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Sparsifying Sums of Norms.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Pure Entropic Regularization for Metrical Task Systems.

[BibT_eX]

[DOI]

Christian Coester

Theory Comput., 2022

Multiscale Entropic Regularization for MTS on General Metric Spaces.

[BibT_eX]

[DOI]

Farzam Ebrahimnejad

Fernando G. S. L. Brandão

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

2020

Adversarial Hypothesis Testing and a Quantum Stein's Lemma for Restricted Measurements.

[BibT_eX]

[DOI]

Aram W. Harrow

Yuval Peres

IEEE Trans. Inf. Theory, 2020

2019

Flow-Cut Gaps and Face Covers in Planar Graphs.

[BibT_eX]

[DOI]

Havana Rika

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

k-server via multiscale entropic regularization.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Fusible HSTs and the Randomized k-Server Conjecture.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Covering the Large Spectrum and Generalized Riesz Products.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2017

Separators in Region Intersection Graphs.

[BibT_eX]

[DOI]

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

2016

Graph Bandwidth.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Approximate Constraint Satisfaction Requires Large LP Relaxations.

[BibT_eX]

[DOI]

J. ACM, 2016

2015

A node-capacitated Okamura-Seymour theorem.

[BibT_eX]

[DOI]

Manor Mendel

Math. Program., 2015

Lower Bounds on the Size of Semidefinite Programming Relaxations.

[BibT_eX]

[DOI]

Prasad Raghavendra

David Steurer

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Talagrand's Convolution Conjecture on Gaussian Space.

[BibT_eX]

[DOI]

Ronen Eldan

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities.

[BibT_eX]

[DOI]

Shayan Oveis Gharan

Luca Trevisan

J. ACM, 2014

On the Power of Symmetric LP and SDP Relaxations.

[BibT_eX]

[DOI]

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

Dimension Reduction for Finite Trees in ℓ 1.

[BibT_eX]

[DOI]

Arnaud de Mesmay

Discret. Comput. Geom., 2013

A lower bound on dimension reduction for trees in \ell_1

[BibT_eX]

[DOI]

CoRR, 2013

Pathwidth, trees, and random embeddings.

[BibT_eX]

[DOI]

Comb., 2013

On the 2-sum embedding conjecture.

[BibT_eX]

[DOI]

Daniel E. Poore

Proceedings of the Symposium on Computational Geometry 2013, 2013

2012

Multi-way spectral partitioning and higher-order cheeger inequalities.

[BibT_eX]

[DOI]

Shayan Oveis Gharan

Luca Trevisan

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Dimension reduction for finite trees in l1.

[BibT_eX]

[DOI]

Arnaud de Mesmay

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Eigenvectors of random graphs: Nodal Domains.

[BibT_eX]

[DOI]

Yael Dekel

Nathan Linial

Random Struct. Algorithms, 2011

On the Optimality of Gluing over Scales.

[BibT_eX]

[DOI]

Alexander Jaffe

Discret. Comput. Geom., 2011

Dimension reduction for finite trees in L_1

[BibT_eX]

[DOI]

Arnaud de Mesmay

CoRR, 2011

A Reformulation of the Arora-Rao-Vazirani Structure Theorem

[BibT_eX]

[DOI]

Sanjeev Arora

Sushant Sachdeva

CoRR, 2011

Near-optimal distortion bounds for embedding doubling spaces into L1.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Cover times, blanket times, and majorizing measures.

[BibT_eX]

[DOI]

Jian Ding

Yuval Peres

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010

Special Section On Foundations of Computer Science.

[BibT_eX]

[DOI]

Christopher Umans

SIAM J. Comput., 2010

Eigenvalue bounds, spectral partitioning, and metrical deformations via flows.

[BibT_eX]

[DOI]

Punyashloka Biswal

Satish Rao

J. ACM, 2010

Metric uniformization and spectral bounds for graphs

[BibT_eX]

[DOI]

CoRR, 2010

Randomly removing g handles at once.

[BibT_eX]

[DOI]

Glencora Borradaile

Comput. Geom., 2010

Almost Euclidean subspaces of l 1N VIA expander codes.

[BibT_eX]

[DOI]

Alexander A. Razborov

Comb., 2010

Bilipschitz snowflakes and metrics of negative type.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Genus and the Geometry of the Cut Graph.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

Volume Distortion for Subsets of Euclidean Spaces.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2009

On the geometry of graphs with a forbidden minor.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Higher Eigenvalues of Graphs.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Expander codes over reals, Euclidean sections, and compressed sensing.

[BibT_eX]

[DOI]

Avi Wigderson

Proceedings of the 47th Annual Allerton Conference on Communication, 2009

2008

Graph Bandwidth.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Improved Approximation Algorithms for Minimum Weight Vertex Separators.

[BibT_eX]

[DOI]

Uriel Feige

MohammadTaghi Hajiaghayi

SIAM J. Comput., 2008

Coarse Differentiation and Multi-flows in Planar Graphs.

[BibT_eX]

[DOI]

Prasad Raghavendra

Electron. Colloquium Comput. Complex., 2008

Almost Euclidean subspaces of lN1 via expander codes.

[BibT_eX]

[DOI]

Alexander A. Razborov

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals.

[BibT_eX]

[DOI]

Avi Wigderson

Proceedings of the Approximation, 2008

2007

An improved approximation ratio for the minimum linear arrangement problem.

[BibT_eX]

[DOI]

Uriel Feige

Inf. Process. Lett., 2007

Almost Euclidean subspaces of ℓ1N via expander codes.

[BibT_eX]

[DOI]

Alexander A. Razborov

Electron. Colloquium Comput. Complex., 2007

Fréchet Embeddings of Negative Type Metrics.

[BibT_eX]

[DOI]

Sanjeev Arora

Discret. Comput. Geom., 2007

The intrinsic dimensionality of graphs.

[BibT_eX]

[DOI]

Comb., 2007

Vertex cuts, random walks, and dimension reduction in series-parallel graphs.

[BibT_eX]

[DOI]

Bo Brinkman

Adriana Karagiozova

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

Trees and Markov convexity.

[BibT_eX]

[DOI]

Yuval Peres

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Lp metrics on the Heisenberg group and the Goemans-Linial conjecture.

[BibT_eX]

[DOI]

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Algorithms on negatively curved spaces.

[BibT_eX]

[DOI]

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Volume distortion for subsets of Euclidean spaces: extended abstract.

[BibT_eX]

[DOI]

Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

2005

The black-box complexity of nearest-neighbor search.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Metric structures in L1: dimension, snowflakes, and average distortion.

[BibT_eX]

[DOI]

Manor Mendel

Eur. J. Comb., 2005

Euclidean distortion and the sparsest cut.

[BibT_eX]

[DOI]

Sanjeev Arora

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

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

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

Hardness of Approximation for Vertex-Connectivity Network Design Problems.

[BibT_eX]

[DOI]

Guy Kortsarz

SIAM J. Comput., 2004

Navigating nets: simple algorithms for proximity search.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Metric Structures in L1: Dimension, Snowflakes, and Average Distortion.

[BibT_eX]

[DOI]

Manor Mendel

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Measured Descent: A New Embedding Method for Finite Metrics.

[BibT_eX]

[DOI]

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

Bounded Geometries, Fractals, and Low-Distortion Embeddings.

[BibT_eX]

[DOI]

Anupam Gupta