Professor
Paul G. Allen School of Computer Science and Engineering
University of Washington
Paul G. Allen Center, Room 640
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] | Ronen Eldan and James R. Lee. Regularization under diffusion and anticoncentration of the information content. Duke Math. J., 167(5):969--993, 2018. |
[2] | James R. Lee. Discrete uniformizing metrics on distributional limits of sphere packings. Geom. Funct. Anal., 28(4):1091--1130, 2018. |
[3] | 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. |
[4] | James R. Lee. Covering the large spectrum and generalized Riesz products. SIAM J. Discrete Math., 31(1):562--572, 2017. |
[5] | Ronen Eldan, James R. Lee, and Joseph Lehec. Transport-entropy inequalities and curvature in discrete-space Markov chains. In A journey through discrete mathematics, pages 391--406. Springer, 2017. |
[6] | 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. |
[7] | 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. |
[8] | James R. Lee, Manor Mendel, and Mohammad Moharrami. A node-capacitated Okamura-Seymour theorem. Math. Program., 153(2, Ser. A):381--415, 2015. |
[9] | 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. |
[10] | 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. |
[11] | Jian Ding, James R. Lee, and Yuval Peres. Markov type and threshold embeddings. Geom. Funct. Anal., 23(4):1207--1229, 2013. |
[12] | James R. Lee, Arnaud de Mesmay, and Mohammad Moharrami. Dimension reduction for finite trees in _{1}. Discrete Comput. Geom., 50(4):977--1032, 2013. |
[13] | James R. Lee and Anastasios Sidiropoulos. Pathwidth, trees, and random embeddings. Combinatorica, 33(3):349--374, 2013. |
[14] | James R. Lee, Manor Mendel, and Mohammad Moharrami. On the Hausdorff dimension of ultrametric subsets in R^{n}. Fund. Math., 218(3):285--290, 2012. |
[15] | Jian Ding, James R. Lee, and Yuval Peres. Cover times, blanket times, and majorizing measures. Ann. of Math. (2), 175(3):1409--1471, 2012. |
[16] | Alexander Jaffe, James R. Lee, and Mohammad Moharrami. On the optimality of gluing over scales. Discrete Comput. Geom., 46(2):270--282, 2011. |
[17] | 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. |
[18] | Yael Dekel, James R. Lee, and Nathan Linial. Eigenvectors of random graphs: nodal domains. Random Structures Algorithms, 39(1):39--58, 2011. |
[19] | James R. Lee and Prasad Raghavendra. Coarse differentiation and multi-flows in planar graphs. Discrete Comput. Geom., 43(2):346--362, 2010. |
[20] | Venkatesan Guruswami, James R. Lee, and Alexander Razborov. Almost Euclidean subspaces of ^{N}_{1} via expander codes. Combinatorica, 30(1):47--68, 2010. |
[21] | Glencora Borradaile, James R. Lee, and Anastasios Sidiropoulos. Randomly removing g handles at once. Comput. Geom., 43(8):655--662, 2010. |
[22] | 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. |
[23] | James R. Lee, Assaf Naor, and Yuval Peres. Trees and Markov convexity. Geom. Funct. Anal., 18(5):1609--1659, 2009. |
[24] | James R. Lee. Volume distortion for subsets of Euclidean spaces. Discrete Comput. Geom., 41(4):590--615, 2009. |
[25] | Uriel Feige, Mohammadtaghi Hajiaghayi, and James R. Lee. Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput., 38(2):629--657, 2008. |
[26] | Sanjeev Arora, James R. Lee, and Assaf Naor. Euclidean distortion and the sparsest cut. J. Amer. Math. Soc., 21(1):1--21, 2008. |
[27] | Sanjeev Arora, James R. Lee, and Assaf Naor. Fréchet embeddings of negative type metrics. Discrete Comput. Geom., 38(4):726--739, 2007. |
[28] | Robert Krauthgamer and James R. Lee. The intrinsic dimensionality of graphs. Combinatorica, 27(5):551--585, 2007. |
[29] | Uriel Feige and James R. Lee. An improved approximation ratio for the minimum linear arrangement problem. Inform. Process. Lett., 101(1):26--29, 2007. |
[30] | James R. Lee and Assaf Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160(1):59--95, 2005. |
[31] | 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. |
[32] | 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. |
[33] | Robert Krauthgamer and James R. Lee. The black-box complexity of nearest-neighbor search. Theoret. Comput. Sci., 348(2-3):262--276, 2005. |
[34] | James R. Lee and Assaf Naor. Absolute Lipschitz extendability. C. R. Math. Acad. Sci. Paris, 338(11):859--862, 2004. |
[35] | 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. |
[36] | 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. |
[1] | 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, pages 3--16, 2018. |
[2] | 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, pages 1:1--1:8, 2017. |
[3] | 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, pages 1395--1408, 2015. |
[4] | 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, pages 567--576, 2015. |
[5] | 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, pages 13--21, 2014. |
[6] | 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, pages 183--194, 2014. |
[7] | 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, pages 197--206, 2013. |
[8] | 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, pages 350--359, 2013. |
[9] | 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, pages 495--504, 2013. |
[10] | James R. Lee, Arnaud de Mesmay, and Mohammad Moharrami. Dimension reduction for finite trees in l_1. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 43--50, 2012. |
[11] | 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, pages 1117--1130, 2012. |
[12] | 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, pages 61--70, 2011. |
[13] | 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, pages 765--772, 2011. |
[14] | 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, pages 193--201, 2010. |
[15] | 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, pages 621--630, 2010. |
[16] | 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, pages 190--201, 2009. |
[17] | 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, pages 371--376, 2009. |
[18] | 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, pages 735--744, 2009. |
[19] | 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, pages 245--254, 2009. |
[20] | 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, pages 444--454, 2008. |
[21] | 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, pages 751--760, 2008. |
[22] | 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, pages 761--770, 2008. |
[23] | Venkatesan Guruswami, James R. Lee, and Alexander A. Razborov. Almost euclidean subspaces of l^n_1 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, pages 353--362, 2008. |
[24] | 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, pages 228--241, 2007. |
[25] | 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, pages 436--448, 2007. |
[26] | 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, pages 621--630, 2007. |
[27] | 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, pages 207--216, 2006. |
[28] | James R. Lee and Assaf Naor. Lp 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, pages 99--108, 2006. |
[29] | 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, pages 119--132, 2006. |
[30] | 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, pages 1028--1037, 2006. |
[31] | 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, pages 92--101, 2005. |
[32] | 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, pages 553--562, 2005. |
[33] | 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, pages 563--572, 2005. |
[34] | 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, pages 434--443, 2004. |
[35] | 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, pages 858--869, 2004. |
[36] | James R. Lee, Manor Mendel, and Assaf Naor. Metric structures in L1: dimension, snowflakes, and average distortion. In LATIN 2004: Theoretical Informatics, 6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004, Proceedings, pages 401--412, 2004. |
[37] | 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, pages 798--807, 2004. |
[38] | 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, pages 534--543, 2003. |
[39] | 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, pages 438--447, 2003. |
[40] | 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, pages 185--199, 2002. |