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, pg. 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 $\ell_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 $\mathbb{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 $\ell^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, Mohammad Taghi 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] | 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. |
[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] | 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. |
[4] | 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. |
[5] | 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. |
[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] | 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. |
[11] | 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. |
[12] | 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. |
[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, 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. |
[15] | 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. |
[16] | 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. |
[17] | 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. |
[18] | 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. |
[19] | 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. |
[20] | 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. |
[21] | 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. |
[22] | 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. |
[23] | 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. |
[24] | 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. |
[25] | 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. |
[26] | 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. |
[27] | 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. |
[28] | 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. |
[29] | 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. |
[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] | 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. |
[32] | 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. |
[33] | 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. |
[34] | 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. |
[35] | 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. |
[36] | 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. |
[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] | 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. |
[39] | 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. |
[40] | 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. |
[41] | 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. |
[42] | 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. |
[43] | 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. |
[44] | 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. |
[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. |