Curriculum Vitae

James R. Lee

Professor
Paul G. Allen School of Computer Science and Engineering
University of Washington

Paul G. Allen Center, Room 574
Phone: +1 510 847 6646
E-mail: jrl@cs.washington.edu
Web: http://www.cs.washington.edu/homes/jrl/

Employment

• September 2006—present:
Professor of Computer Science, University of Washington
Associate Professor, September 2011—August 2016
Assistant Professor, September 2006—August 2011
• March—June 2017:
Visiting Researcher, Microsoft Research (Redmond)
• August 2007—present:
Consulting Researcher, Microsoft Research (Redmond)
• August 2005—September 2006
Postdoctoral Researcher, Institute for Advanced Study, Princeton

Research interests

Algorithms, complexity, and optimization. Geometry and analysis at the interface between the continuous and discrete. Probability and stochastic processes.

Education

• University of California at Berkeley

Ph.D., Computer Science, May 2005
Thesis: Metric geometry, geometric algorithms, and combinatorial optimization

• Purdue University, West Lafayette, Indiana

B.S. (Honors), Mathematics & Computer Science (1997—2001)

Honors and awards

• Simons Investigator, 2017—
• UW ACM Undergraduate Teaching Award, 2015
• STOC Best Paper Award, 2015
Lower bounds on the size of semidefinite programming relaxations (with P. Raghavendra and D. Steurer)
• Sloan Research Fellowship, 2009
• NSF CAREER Award, 2007
• Institute for Advanced Study Fellowship, 2005—2006
• NSF Graduate Research Fellow, 2002—2005
• The Outstanding Senior in Mathematics Award, School of Science, Purdue Univ., 2001
• Golomb Prize for the Outstanding Undergraduate in Mathematics, Purdue Univ., 2001

Professional activities

• Editor, Forum of Mathematics Sigma and Pi (TCS cluster), 2017—present
• Associate editor, SIAM Journal on Computing, 2015—present
• Scientific Advisory Board, Simons Institute for Theoretical Computer Science, 2017—2019
• Associate editor, SIAM Journal on Discrete Mathematics, 2015—2017
• Guest editor, SIAM Journal on Computing, special issue for papers from FOCS 2007
• Conference and workshop organization:
• Technical logistics co-organizer for ITCS 2021, Jan 6-8, 2021.
• Co-organizer, workshop on "Concentration of Measure Phenomena" at the Simons Institute for the Theory of Computing, Berkeley, CA, October, 2020.
• Co-organizer, FOCS 2017 and 2018 Workshops and Tutorials
• Co-organizer, workshop on "Algebraic and spectral graph theory" at the Banff International Research Institute. July 31—August 5, 2016
• Co-organizer, UW-MSR Summer Institute on "Learning, optimization, and stochastic processes." Alderbook, WA. August 23—26, 2015
• Co-organizer and chair, semester program on "Algorithmic Spectral Graph Theory" at the Simons Institute for the Theory of Computing, Berkeley, CA, Fall 2014
• Co-organizer of the workshop "Spectral algorithms: From theory to practice" at the Simons Institute for the Theory of Computing, Berkeley, CA, October 27—31, 2015
• Organizer of the invited workshop "$L_1$ embeddings and flow-cut gaps" at the ACM Symposium on Computational Geometry, 2012
• Co-organizer, semester program on "Metric geometry, algorithms, and groups" at the Centre Emile Borel (Institute Henri Poincaré), Paris, France, Winter 2011
• Program committees:
• FOCS 2022: 63rd Annual Symposium on the Foundations of Computer Science
• ITCS 2021 (PC Chair): The 12th Innovations in Theoretical Computer Science conference
• SODA 2021: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms
• APPROX 2018: 21st Workshop on Approximation Algorithms for Combinatorial Optimization
• STOC 2017: 49th Annual Symposium on the Theory of Computing
• FOCS 2014: 55th Annual Symposium on the Foundations of Computer Science
• ICALP 2014: 41st Annual International Colloquium on Automata and Complexity
• SODA 2014: 25th Annual ACM-SIAM Symposium on Discrete Algorithms
• ISAAC 2013: 24th International Symposium on Algorithms and Computation
• ESA 2011: 19th Annual European Symposium on Algorithms
• FOCS 2010: 51st Annual Symposium on Foundations of Computer Science
• COCOON 2010: 16th Annual International Computing and Combinatorics Conference
• SODA 2009: 20th Annual ACM-SIAM Symposium on Discrete Algorithms
• FOCS 2007: 48th Annual Symposium on Foundations of Computer Science
• APPROX 2006: 9th Workshop on Approximation Algorithms for Combinatorial Optimization
• Tutorials and summer schools:
• Invited lectures on "Semidefinite extended formulations and sums of squares" at the Summer School on Combinatorial Optimization, Hausdorff Institute for Mathematics, Bonn, Germany. September, 2015.
• Co-organizer of the "Experience Theory Project" for advanced graduate students. Hosted at UW and Microsoft Research, Summer, 2012
• Co-organizer of the "Experience Theory Project" for talented undergraduates. Hosted at UW and Microsoft Research, Summer, 2010
• Co-organizer of a summer school on "Analysis and geometry in the theory of computing" at Indiana University, Summer 2009

Research funding

• NSF CCF-2007079
Metric information theory, online learning, and competitive analysis. Aug, 2020—Aug, 2023
• NSF NRT-2021540, co-PI
NRT-QL: Accelerating Quantum-Enabled Technologies. Sep, 2020—Aug, 2025
• Simons Investigator Award
Aug, 2017—present
• NSF CCF-1616297
Entropy maximization in approximation, learning, and complexity. Sep, 2016—Aug, 2019.
• NSF CCF-1407779
On the power of mathematical programming in combinatorial optimization. Jul, 2014—May 2018.
• NSF CCF-1217256
Metric geometry for combinatorial problems. Aug, 2012—Jul, 2015.
• Sloan Research Fellowship
Aug, 2009--Aug, 2012
• NSF CCF-0915251
Spectral analysis, spectral algorithms, and beyond. Sep, 2009—Aug, 2012.
• NSF CCF-0644037
Geometric phenomena in algorithms and complexity. Feb, 2007—May 2011.
• BSF #2006052
Some complexity issues between P and NP. Jun, 2007—Jun, 2010.

• Ph.D. students
• Ewin Tang, 2018—
• Alexander B. Jaffe, 2007—2013
• Punyashloka Biswal, 2007—2011 (Masters)
• Christian Coester (Oxford), Aug-Dec, 2018
• Andrea Francke (ETH Zurich)
• Teng Qin (ENS Paris)
• Sean Hung, 2017—2018
• Austin Stromme (now at MIT), 2015—2018
• Yueqi Sheng (now at Harvard), 2015—2016
• Ben Eggers, 2014—2016
• Arnaud de Mesmay, 2011
• Will Johnson, 2010
• Justin Vincent, 2006
• Postdocs
• Aaron Schild, Sep 2019—Aug 2020.
• Ronen Eldan, Aug—Mar, 2015.
• Tsz Chiu Kwok, Aug—Dec, 2014.
• Jian Ding, Sep—Dec, 2011.
• Ph.D. exam committees
• Alireza Rezaei
• Shirshendu Ganguly (Math)
• David J. Rosenbaum
• Elizabeth Crosson (Physics)
• Matthew Scott Junge (Math)
• Joel W. Barnes (Math)
• Stephen D. Lewis (Math)
• Dang-Trinh Huynh-Ngoc
• Michael Goff (Math)

Long-term invited visits

• Program member, Simons Institute for the Theory of Computing, October—November, 2017.
• Program organizer, Simons Institute for the Theory of Computing, August—December, 2014.
• Visiting Scholar, U. C. Berkeley, September 2012—August, 2013.
• Visiting Professor, Institute Henri Poincaré, Paris, France, January—March, 2011.
• Institute for Pure and Applied Mathematics, Los Angeles, California, January—February, 2008.
• Massachusetts Institute of Technology, August—September, 2007.
• Université Paris-Sud 11, Orsay, France, June—July, 2007.
• Hebrew University, Jerusalem, December—January, 2006.

Invited lectures

• Selected:
• Plenary Speaker, 41st Conference on Stochastic Processes and Applications (SPA). Evanston, IL, Jul, 2019.
• Invited survey talk, 4th Conference on Highlights of Algorithms (HALG). Copenhagen, Jun, 2019.
• Plenary Speaker, 20th Annual Conference on Quantum Information Processing (QIP). Seattle, WA, Jan, 2017.
• Plenary Lecture Series, Workshop on Positive Semidefinite Rank. Institute for Mathematical Sciences, Singapore, Feb, 2016.
• Bernoulli Lecture. EPFL, Dec, 2015.
• Charles River Lectures on Probability and Related Topics. Harvard and Microsoft Research, Oct, 2015.
• Avner Magen Memorial Lecture. Fields Institute, Toronto, May, 2015.
• Keynote Lectures, Topics in Differential Geometry and its Discretizations. Tohoku University, Jan, 2015.
• Open Lecture. Simons Institute for the Theory of Computing, Dec, 2014.
• Other recent lectures (2014—):
• USC Probability & Statistics seminar (online), Oct, 2020
• Random Geometry and Statistical Physics seminar (online), Sep, 2020
• Percolation Today seminar, ETH (online), Jun, 2020
• Geometric functional analysis and probability seminar, Weizmann University, Jan, 2020
• Games, Optimization, and Optimism: in honor of Uri Feige, Weizmann University, Jan, 2020
• Plenary speaker, Theory-Fest, Tel Aviv University, Dec, 2019
• Geometry and Analysis: Celebrating the mathematics of Pierre Pansu, Oxford University, Sep, 2019
• "Bridging continuous and discrete optimization" reunion workshop, Simons Institute, Dec, 2018
• Probability seminar, UC Berkeley, Nov, 2018
• Horowitz seminar, Tel Aviv University, Oct 2018
• Math colloquium, Tel Aviv University, Oct 2018
• Conference on Random walks on symmetric structures, IIAS, Jerusalem, Oct, 2018
• Workshop on Analytic techniques in TCS, Oaxaca, Mexico, Aug, 2018
• Workshop on Optimization, Complexity, and Invariant Theory, IAS, Princeton, Jun, 2018
• Conference on High-dimensional combinatorics, IIAS, Jerusalem, Apr, 2018
• Theory seminar, UC Berkeley, Apr, 2018
• Workshop on Approximation algorithms and Hardness of Approximation, Banff, CA, Nov, 2017
• Workshop on Hierarchies, Extended formulations, and Matrix-analytic techniques, Simons Institute, Nov, 2017
• Elegance in Probability—Conference in honor of Russ Lyons’ 60th, Tel Aviv, Sep, 2017
• Workshop on Proof Complexity and Beyond, Oberwolfach, Aug 2017
• Bellairs workshop on Data, Learning, and Optimization, Barbados, Apr, 2017
• Math colloquium, University of Chicago, Mar 2017
• CS Theory seminar, University of Chicago, Mar 2017
• Rainwater seminar, University of Washington, Jan 2017
• Probability seminar, UBC, October, 2016
• Conference on the Mathematics of Jiří Matoušek, Prague, July, 2016.
• Theory seminar, Caltech, May, 2016.
• Simons Workshop on Analysis of Boolean Functions, Bavaria, Germany, Apr, 2016.
• Probability seminar, University of Washington, Mar 2016.
• Data Science & Society seminar, University of Washington, Mar, 2016.
• Workshop on Counting Complexity and Phase Transitions, Simons Institute, Berkeley, CA, Feb, 2016.
• Plenary Lecture, Workshop on Relaxations and Polyhedral Methods. University of Bonn, Nov, 2015.
• Workshop on Convexity, Probability, and Discrete Structures, University Paris-Est Marne-La-Vallée, Oct, 2015.
• Workshop on Graphs, Groups, and Stochastic Processes, BIRS, Banff, CA, Jun, 2015.
• Probability seminar, Stanford University, May, 2015
• Bellairs Workshop on Combinatorial Optimization, Barbados, Apr, 2015.
• Workshop on the Power of Randomness in Computation, Georgia Tech, Mar, 2015.
• Limitations of Convex Programming: Extended formulatins and PSD rank, Dagstuhl, Germany, Feb, 2015.
• Probability seminar, University of Chicago, Feb, 2015.
• Theory of Computation seminar, University of Chicago, Feb, 2015.
• Real Analysis Reunion Workshop, Simons Institute, Berkeley, CA, Dec, 2014.
• Workshop on Fast Algorithms via Spectral Methods, Simons Institute, Berkeley, CA, Nov, 2014.
• Combinatorics seminar, University of Bristol, UK, Nov, 2014.
• Workshop on Combinatorial Optimization, Oberwolfach, Germany, Nov, 2014.
• Discrete Mathematics seminar, Institute for Advanced Study, Princeton, Nov, 2014.
• Industry Day, Simons Institute, Berkeley, CA, Nov, 2014.
• Probability seminar, UC Berkeley, Oct, 2014.
• Theory lunch, UC Berkeley, Oct, 2014.
• Combinatorics seminar, UC Berkeley, Sep, 2014.
• Algorithms seminar, École Normale Supérieure, Paris, Sep, 2014.
• 5th Cargèse Workshop on Combinatorial Optimization, Cargese, France, Sep, 2014.
• Workshop on Approximation and Hardness of Approximation, BIRS, Banff, CA, Aug, 2014.
• Workshop on Graphs, Groups, and Stochastic Processes, Renyi Institute, Budapest, Jun, 2014.

Publications

Journal papers

 [1] Shirshendu Ganguly and James R. Lee. Chemical subdiffusivity of critical 2D percolation. Comm. Math. Phys, 389(2):695—714, 2022. [2] Farzam Ebrahimnejad and James R. Lee. On planar graphs of uniform polynomial growth. Probab. Theory Relat. Fields, 180(3):955—984, 2021. [3] Sébastien Bubeck, Michael B. Cohen, James R. Lee, and Yin Tat Lee. Metrical task systems on trees via mirror descent and unfair gluing. SIAM J. Comput., 50(3):909—923, 2021. [4] James R. Lee. Conformal growth rates and spectral geometry on distributional limits of graphs. Ann. Probab., 49(6):2671—2731, 2021. [5] F. G. S. L. Brandão, A. W. Harrow, J. R. Lee, and Y. Peres. Adversarial hypothesis testing and a quantum stein’s lemma for restricted measurements. IEEE Transactions on Information Theory, 66(8):5037—5054, 2020. [6] James R. Lee. Discrete uniformizing metrics on distributional limits of sphere packings. Geom. Funct. Anal., 28(4):1091—1130, 2018. [7] Ronen Eldan and James R. Lee. Regularization under diffusion and anticoncentration of the information content. Duke Math. J., 167(5):969—993, 2018. [8] Ronen Eldan, James R. Lee, and Joseph Lehec. Transport-entropy inequalities and curvature in discrete-space Markov chains. In A journey through discrete mathematics, pg. 391—406. Springer, 2017. [9] James R. Lee. Covering the large spectrum and generalized Riesz products. SIAM J. Discrete Math., 31(1):562—572, 2017. [10] Shirshendu Ganguly, James R. Lee, and Yuval Peres. Diffusive estimates for random walks on stationary random graphs of polynomial growth. Geom. Funct. Anal., 27(3):596—630, 2017. [11] Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer. Approximate constraint satisfaction requires large LP relaxations. J. ACM, 63(4):Art. 34, 22, 2016. [12] James R. Lee, Yuval Peres, and Charles K. Smart. A Gaussian upper bound for martingale small-ball probabilities. Ann. Probab., 44(6):4184—4197, 2016. [13] James R. Lee, Manor Mendel, and Mohammad Moharrami. A node-capacitated Okamura-Seymour theorem. Math. Program., 153(2, Ser. A):381—415, 2015. [14] James R. Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order Cheeger inequalities. J. ACM, 61(6):Art. 37, 30, 2014. [15] James R. Lee and Anastasios Sidiropoulos. Pathwidth, trees, and random embeddings. Combinatorica, 33(3):349—374, 2013. [16] James R. Lee, Arnaud de Mesmay, and Mohammad Moharrami. Dimension reduction for finite trees in $\ell_1$. Discrete Comput. Geom., 50(4):977—1032, 2013. [17] Jian Ding, James R. Lee, and Yuval Peres. Markov type and threshold embeddings. Geom. Funct. Anal., 23(4):1207—1229, 2013. [18] James R. Lee and Yuval Peres. Harmonic maps on amenable groups and a diffusive lower bound for random walks. Ann. Probab., 41(5):3392—3419, 2013. [19] Jian Ding, James R. Lee, and Yuval Peres. Cover times, blanket times, and majorizing measures. Ann. of Math. (2), 175(3):1409—1471, 2012. [20] James R. Lee, Manor Mendel, and Mohammad Moharrami. On the Hausdorff dimension of ultrametric subsets in $\mathbb{R}^n$. Fund. Math., 218(3):285—290, 2012. [21] Yael Dekel, James R. Lee, and Nathan Linial. Eigenvectors of random graphs: nodal domains. Random Structures Algorithms, 39(1):39—58, 2011. [22] Jonathan A. Kelner, James R. Lee, Gregory N. Price, and Shang-Hua Teng. Metric uniformization and spectral bounds for graphs. Geom. Funct. Anal., 21(5):1117—1143, 2011. [23] Alexander Jaffe, James R. Lee, and Mohammad Moharrami. On the optimality of gluing over scales. Discrete Comput. Geom., 46(2):270—282, 2011. [24] Punyashloka Biswal, James R. Lee, and Satish Rao. Eigenvalue bounds, spectral partitioning, and metrical deformations via flows. J. ACM, 57(3):Art. 13, 23, 2010. [25] Glencora Borradaile, James R. Lee, and Anastasios Sidiropoulos. Randomly removing $g$ handles at once. Comput. Geom., 43(8):655—662, 2010. [26] Venkatesan Guruswami, James R. Lee, and Alexander Razborov. Almost Euclidean subspaces of $\ell^N_1$ via expander codes. Combinatorica, 30(1):47—68, 2010. [27] James R. Lee and Prasad Raghavendra. Coarse differentiation and multi-flows in planar graphs. Discrete Comput. Geom., 43(2):346—362, 2010. [28] James R. Lee. Volume distortion for subsets of Euclidean spaces. Discrete Comput. Geom., 41(4):590—615, 2009. [29] James R. Lee, Assaf Naor, and Yuval Peres. Trees and Markov convexity. Geom. Funct. Anal., 18(5):1609—1659, 2009. [30] Sanjeev Arora, James R. Lee, and Assaf Naor. Euclidean distortion and the sparsest cut. J. Amer. Math. Soc., 21(1):1—21, 2008. [31] Uriel Feige, Mohammad Taghi Hajiaghayi, and James R. Lee. Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput., 38(2):629—657, 2008. [32] Uriel Feige and James R. Lee. An improved approximation ratio for the minimum linear arrangement problem. Inform. Process. Lett., 101(1):26—29, 2007. [33] Robert Krauthgamer and James R. Lee. The intrinsic dimensionality of graphs. Combinatorica, 27(5):551—585, 2007. [34] Sanjeev Arora, James R. Lee, and Assaf Naor. Fréchet embeddings of negative type metrics. Discrete Comput. Geom., 38(4):726—739, 2007. [35] Robert Krauthgamer and James R. Lee. The black-box complexity of nearest-neighbor search. Theoret. Comput. Sci., 348(2-3):262—276, 2005. [36] R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. Measured descent: a new embedding method for finite metrics. Geom. Funct. Anal., 15(4):839—858, 2005. [37] James R. Lee, Manor Mendel, and Assaf Naor. Metric structures in $L_1$: dimension, snowflakes, and average distortion. European J. Combin., 26(8):1180—1190, 2005. [38] James R. Lee and Assaf Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160(1):59—95, 2005. [39] Guy Kortsarz, Robert Krauthgamer, and James R. Lee. Hardness of approximation for vertex-connectivity network design problems. SIAM J. Comput., 33(3):704—720, 2004. [40] J. R. Lee and A. Naor. Embedding the diamond graph in $L_p$ and dimension reduction in $L_1$. Geom. Funct. Anal., 14(4):745—747, 2004. [41] James R. Lee and Assaf Naor. Absolute Lipschitz extendability. C. R. Math. Acad. Sci. Paris, 338(11):859—862, 2004.

Conference papers

 [1] Robert Krauthgamer, James R. Lee, and Havana Rika. Flow-cut gaps and face covers in planar graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pg. 525—534. SIAM, Philadelphia, PA, 2019. [2] Sébastien Bubeck, Michael B. Cohen, James R. Lee, and Yin Tat Lee. Metrical task systems on trees via mirror descent and unfair gluing. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pg. 89—97. SIAM, Philadelphia, PA, 2019. [3] Christian Coester and James R. Lee. Pure entropic regularization for metrical task systems. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, pg. 835—848, 2019. [4] Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Madry. $k$-server via multiscale entropic regularization. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pg. 3—16, 2018. [5] James R. Lee. Fusible HSTs and the randomized $k$-server conjecture. In 59th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2018, pg. 438—449. IEEE Computer Soc., Los Alamitos, CA, 2018. [6] James R. Lee. Separators in region intersection graphs. In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, pg. 1:1—1:8, 2017. [7] James R. Lee, Prasad Raghavendra, and David Steurer. Lower bounds on the size of semidefinite programming relaxations. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pg. 567—576, 2015. [8] Ronen Eldan and James R. Lee. Talagrand's convolution conjecture on Gaussian space. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pg. 1395—1408, 2015. [9] James R. Lee, Prasad Raghavendra, and David Steurer. Lower bounds on the size of semidefinite programming relaxations. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pg. 567—576, 2015. [10] Fernando G. S. L. Brandão, Aram Wettroth Harrow, James R. Lee, and Yuval Peres. Adversarial hypothesis testing and a quantum Stein's lemma for restricted measurements. In Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pg. 183—194, 2014. [11] James R. Lee, Prasad Raghavendra, David Steurer, and Ning Tan. On the power of symmetric LP and SDP relaxations. In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014, pg. 13—21, 2014. [12] James R. Lee, Manor Mendel, and Mohammad Moharrami. A node-capacitated Okamura-Seymour theorem. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pg. 495—504, 2013. [13] Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer. Approximate constraint satisfaction requires large LP relaxations. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pg. 350—359, 2013. [14] James R. Lee and Daniel E. Poore. On the 2-sum embedding conjecture. In Symposuim on Computational Geometry 2013, SoCG '13, Rio de Janeiro, Brazil, June 17-20, 2013, pg. 197—206, 2013. [15] James R. Lee, Shayan Oveis Gharan, and Luca Trevisan. Multi-way spectral partitioning and higher-order Cheeger inequalities. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pg. 1117—1130, 2012. [16] James R. Lee, Arnaud de Mesmay, and Mohammad Moharrami. Dimension reduction for finite trees in $\ell_1$. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pg. 43—50, 2012. [17] James R. Lee and Anastasios Sidiropoulos. Near-optimal distortion bounds for embedding doubling spaces into $L_1$. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pg. 765—772, 2011. [18] Jian Ding, James R. Lee, and Yuval Peres. Cover times, blanket times, and majorizing measures. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pg. 61—70, 2011. [19] James R. Lee and Mohammad Moharrami. Bilipschitz snowflakes and metrics of negative type. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pg. 621—630, 2010. [20] James R. Lee and Anastasios Sidiropoulos. Genus and the geometry of the cut graph. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pg. 193—201, 2010. [21] James R. Lee and Anastasios Sidiropoulos. On the geometry of graphs with a forbidden minor. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pg. 245—254, 2009. [22] Jonathan A. Kelner, James R. Lee, Gregory N. Price, and Shang-Hua Teng. Higher eigenvalues of graphs. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pg. 735—744, 2009. [23] Glencora Borradaile, James R. Lee, and Anastasios Sidiropoulos. Randomly removing $g$ handles at once. In Proceedings of the 25th ACM Symposium on Computational Geometry, Aarhus, Denmark, June 8-10, 2009, pg. 371—376, 2009. [24] Alexander Jaffe, James R. Lee, and Mohammad Moharrami. On the optimality of gluing over scales. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings, pg. 190—201, 2009. [25] Venkatesan Guruswami, James R. Lee, and Alexander A. Razborov. Almost euclidean subspaces of $\ell_1^n$ via expander codes. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pg. 353—362, 2008. [26] Amit Chakrabarti, Alexander Jaffe, James R. Lee, and Justin Vincent. Embeddings of topological graphs: Lossy invariants, linearization, and 2-sums. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pg. 761—770, 2008. [27] Punyashloka Biswal, James R. Lee, and Satish Rao. Eigenvalue bounds, spectral partitioning, and metrical deformations via flows. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pg. 751—760, 2008. [28] Venkatesan Guruswami, James R. Lee, and Avi Wigderson. Euclidean sections of with sublinear randomness and error-correction over the reals. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008. Proceedings, pg. 444—454, 2008. [29] Bo Brinkman, Adriana Karagiozova, and James R. Lee. Vertex cuts, random walks, and dimension reduction in series- parallel graphs. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pg. 621—630, 2007. [30] Yael Dekel, James R. Lee, and Nathan Linial. Eigenvectors of random graphs: Nodal domains. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, Proceedings, pg. 436—448, 2007. [31] James R. Lee and Prasad Raghavendra. Coarse differentiation and multi-flows in planar graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, Proceedings, pg. 228—241, 2007. [32] James R. Lee, Assaf Naor, and Yuval Peres. Trees and Markov convexity. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pg. 1028—1037, 2006. [33] Robert Krauthgamer and James R. Lee. Algorithms on negatively curved spaces. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pg. 119—132, 2006. [34] James R. Lee and Assaf Naor. $L_p$ metrics on the Heisenberg group and the Goemans-Linial conjecture. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pg. 99—108, 2006. [35] James R. Lee. Volume distortion for subsets of Euclidean spaces: Extended abstract. In Proceedings of the 22nd ACM Symposium on Computational Geometry, Sedona, Arizona, USA, June 5-7, 2006, pg. 207—216, 2006. [36] Uriel Feige, Mohammad Taghi Hajiaghayi, and James R. Lee. Improved approximation algorithms for minimum-weight vertex separators. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pg. 563—572, 2005. [37] Sanjeev Arora, James R. Lee, and Assaf Naor. Euclidean distortion and the Sparsest Cut. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pg. 553—562, 2005. [38] James R. Lee. On distance scales, embeddings, and efficient relaxations of the cut cone. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pg. 92—101, 2005. [39] Robert Krauthgamer and James R. Lee. Navigating nets: simple algorithms for proximity search. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004, pg. 798—807, 2004. [40] James R. Lee, Manor Mendel, and Assaf Naor. Metric structures in $L_1$: Dimension, snowflakes, and average distortion. In LATIN 2004: Theoretical Informatics, 6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004, Proceedings, pg. 401—412, 2004. [41] Robert Krauthgamer and James R. Lee. The black-box complexity of nearest neighbor search. In Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings, pg. 858—869, 2004. [42] Robert Krauthgamer, James R. Lee, Manor Mendel, and Assaf Naor. Measured descent: A new embedding method for finite metrics. In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pg. 434—443, 2004. [43] Robert Krauthgamer and James R. Lee. The intrinsic dimensionality of graphs. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pg. 438—447, 2003. [44] Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pg. 534—543, 2003. [45] Guy Kortsarz, Robert Krauthgamer, and James R. Lee. Hardness of approximation for vertex-connectivity network-design problems. In Approximation Algorithms for Combinatorial Optimization, 5th International Workshop, APPROX 2002, Rome, Italy, September 17-21, 2002, Proceedings, pg. 185—199, 2002.