funk

James R. Lee

email: jrl @ cs dot (obvious)
Associate Professor
Department of Computer Science and Engineering
University of Washington
(contact info at bottom)

I got my PhD in CS from Berkeley, advised by Christos Papadimitriou.
After that, I did a postdoc in Avi's group at the Institute for Advanced Study in Princeton.

Research interests:
Algorithms, complexity, optimization.
High-dimensional geometry, geometry of discrete metric spaces, spectral graph theory, probability.
Applications of geometry and analysis in theoretical computer science.

(not a) blog: tcsmath

teaching:  CSE 599S: Algorithmic Spectral Graph Theory

students:   [Punya Biswal | Alex Jaffe | Mohammad Moharrami]

funding: NSF CAREER Award (CCF 0644037) - Geometric phenomena in algorithms and complexity

NSF CCF-0915251: Spectral analysis, spectral algorithms, and beyond

BSF 2006052 - On some complexity issues between P and NP

         (with Arora, Papadimidtriou, Safra)

Sloan Research Fellowship

committees: APPROX 2006, FOCS 2007, SODA 2009, COCOON 2010, FOCS 2010, ESA 2011.

selected recent papers

Multi-way spectral partitioning and higher-order Cheeger inequalities, with S. Oveis Gharan and L. Trevisan (STOC'12)
Cover times, blanket times, and majorizing measures, with J. Ding and Y. Peres (STOC'11; Annals of Math)
Metric uniformization and spectral bounds for graphs, with J. Kelner, G. Price, and S.-H. Teng (FOCS'09, GAFA)
Pathwidth, trees, and random embeddings, with T. Sidiropoulos (STOC'09)
Eigenvalue bounds, spectral partitioning, and metrical deformations via flows, with P. Biswal and S. Rao (FOCS'08, Journal of the ACM)
Almost Euclidean subspaces of L1n via expander codes, with A. Razborov and V. Guruswami (SODA'08, Combinatorica)

other selected papers

Euclidean distortion and the Sparsest Cut, with S. Arora and A. Naor (STOC'05, Journal of the AMS)
Improved approximation algorithms for minimum-weight vertex separators, with U. Feige and M.-T. Hajiaghayi (STOC'05, SICOMP)
Distance scales, embeddings, and metrics of negative type (SODA'05)
Extending Lipschitz functions via random metric partitions, with A. Naor (Inventiones)
Embedding the diamond graph in Lp and dimension reduction in L1, with A. Naor (GAFA)

some notes

some talks

all papers

  • Multi-way spectral partitioning and higher-order Cheeger inequalities (with S. Oveis Gharan and L. Trevisan) [arxiv]
    To appear, STOC 2012.
  • Dimension reduction for finite trees in L1 (with A. de Mesmay and M. Moharrami) [arxiv]
    To appear, SODA 2012.
  • Near-optimal distortion bounds for embedding doubling spaces into L1 (with A. Sidiropoulos)
    STOC 2011
  • Cover times, blanket times, and majorizing measures (with J. Ding and Y. Peres) [arxiv]
    To appear, Annals of Math. [ STOC 2011 ]
  • Bilipschitz snowflakes and metrics of negative type (with M. Moharrami)
    STOC 2010
  • Genus and the geometry of the cut graph (with T. Sidiropoulos)
    SODA 2010
  • Harmonic maps on amenable groups and a diffusive lower bound for random walks (with Y. Peres) [arxiv]
    To appear, Annals of Probability.
  • On the optimality of gluing over scales (with A. Jaffe and M. Moharrami) [arxiv]
    To appear, Discrete & Computational Geometry. [ APPROX 2009 ]
  • Metric uniformization and spectral bounds for graphs (with J. Kelner, G. Price, and S.-H. Teng) [arxiv]
    Geometric & Functional Analysis (GAFA), 21(5): 1117-1143, 2011.
    Announcement "Higher eigenvalues of graphs" in FOCS 2009.
  • Sparsest Cut on quotients of the hypercube (with A. Kolla)
    submitted, 2009.
  • Randomly removing g handles at once (with G. Borradaile and T. Sidiropoulos) [arxiv]
    Computational Geometry, Theory and Applications, 43(8): 655-662, 2010. [ SoCG 2009 ]
  • Pathwidth, trees, and random embeddings (with T. Sidiropoulos) [arxiv]
    submitted, 2009.
    This paper is part one of the full version of the following extended abstract.
    On the geometry of graphs with a forbidden minor (with T. Sidiropoulos) [ps | pdf]
    STOC 2009
  • Eigenvalue multiplicity and volume growth (with Y. Makarychev) [ps | pdf]
    To appear, Journal of Topology and Analysis.
  • Eigenvalue bounds, spectral partitioning, and metrical deformations via flows (with P. Biswal and S. Rao) [arxiv]
    Journal of the ACM, 57(3): 13(1-23), 2010. [ FOCS 2008 ]
  • Euclidean sections of L1n with sublinear randomness and error-correction over the reals (with V. Guruswami and A. Wigderson) [ps | pdf]
    RANDOM 2008
  • Local moves and lossy invariants in planar graph embeddings (with A. Chakrabarti, A. Jaffe, and J. Vincent) [ps | pdf]
    FOCS 2008
  • Almost Euclidean subspaces of L1n via expander codes (with V. Guruswami and A. Razborov) [ps | pdf]
    Combinatorica, 30(1): 47-68, 2010. [ SODA 2008 ]
  • Eigenvectors of random graphs: Nodal domains (with Y. Dekel and N. Linial) [ps | pdf]
    Random Strucures & Algorithms, 39(1): 39-58, 2011. [ RANDOM 2007 ]
  • Coarse differentiation and planar multi-flows (with P. Raghavendra) [ps | pdf]
    Discrete & Computational Geometry, 43(2): 346-362, 2010. [ APPROX 2007 ]
  • Vertex cuts, random walks, and dimension reduction in series-parallel graphs (with B. Brinkman and A. Karagiozova) [pdf]
    STOC 2007
  • Trees and Markov convexity (with A. Naor and Y. Peres) [arxiv]
    Geometric and Functional Analysis (GAFA), 18(5): 1609-1659, 2009. [ SODA 2006 ]
  • Improved distortion bounds for metrics of negative type
    in preparation, 2006. [comment]
  • Lp metrics on the Heisenberg group and the Goemans-Linial conjecture (with A. Naor) [ps | pdf]
    FOCS 2006
  • Algorithms on negatively curved spaces (with R. Krauthgamer) [ps | pdf]
    FOCS 2006
  • Volume distortion for subsets of Euclidean spaces [ps | pdf]
    Discrete & Computational Geometry, 41(4): 590-615, 2009. [ SoCG 2006 ]

happiness is a warm theorem.

old teaching: CSE 312 Foundations of CS II (Winter'12)
CSE 431 Introduction to the Theory of Computation (Spring'11)
CSE 312: Foundations of CS, II (Autumn'10)
CSE 421 Design and Analysis of Algorithms (Autumn 09)
CSE 521 Design and Analysis of Algorithms (Spring 09)
CSE 599S Analytical and geometric methods in the theory of computation (Fall 08)
CSE 431 Introduction to the Theory of Computation (Spring '08)

CSE 525 Randomized Algorithms & Probabilistic Analysis (Winter'08)

CSE 321 Discrete Structures (Autumn'07)

CSE 525 Randomized algorithms and probabilistic analysis (Spring'07)

CSE 599I Geometric embeddings and high-dimensional phenomena (Winter'07)

CSE 321 Discrete Structures (Autumn'06)

address:
James R. Lee
Department of Computer Science and Engineering
Box 352350
University of Washington
Seattle, WA 98195-2350