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/
Ph.D., Computer Science, May 2005
Advisor: Christos H. Papadimitriou
Thesis: Metric geometry, geometric algorithms, and combinatorial optimization
B.S. (Honors), Mathematics & Computer Science (1997—2001)
[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. |
[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. |