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

students:   [Daniel Poore | 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, SODA 2014.

some recent talks (older talks)

recent papers in spectral graph theory/random walks

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)
Harmonic maps on amenable groups and a diffusive lower bound for random walks, with Y. Peres (Annals of Probability)
Metric uniformization and spectral bounds for graphs, with J. Kelner, G. Price, and S.-H. Teng (FOCS'09, GAFA)
Eigenvalue bounds, spectral partitioning, and metrical deformations via flows, with P. Biswal and S. Rao (FOCS'08, JACM)

recent papers in embeddings/metric geometry

On the 2-sum embedding conjecture, with D. Poore (SoCG'13)
A node-capacitated Okamura-Seymour theorem, with M. Mendel and M. Moharrami (STOC'13)
Markov type and threshold embeddings, with J. Ding and Y. Peres (GAFA)
Dimension reduction for finite trees in L1, with A. de Mesmay and M. Moharrami (SODA'12)
    and A lower bound on dimension ... (with M. Moharrami)
Near-optimal distortion bounds for embedding doubling spaces into L1, with A. Sidiropoulos (STOC'11)
Bilipschitz snowflakes and metrics of negative type, with M. Moharrami (STOC'10)
Pathwidth, trees, and random embeddings, with A. Sidiropoulos (STOC'09, Combinatorica)

some notes

all papers

  • A lower bound on dimension reduction for trees in L1 (with M. Moharrami) [arxiv]
  • On the 2-sum embedding conjecture (with D. Poore)
    To appear, SoCG 2013.
  • On expanders from the action of GL(2,Z) [pdf]
  • A node-capacitated Okamura-Seymour theorem (with M. Mendel and M. Moharrami) [arxiv]
    To appear, STOC 2013.
  • Markov type and threshold embeddings (with J. Ding and Y. Peres) [arxiv]
    To appear, Geometric & Functional Analysis (GAFA).
  • On the Hausdorff dimension of ultrametric subsets in Rn (with M. Mendel and M. Moharrami) [arxiv]
    Fundamenta Mathematicae, 218: 285-290, 2012.
  • A note on mixing times of planar random walks (with T. Qin) [arxiv]

  • Multi-way spectral partitioning and higher-order Cheeger inequalities (with S. Oveis Gharan and L. Trevisan) [arxiv]
    STOC 2012.
  • Dimension reduction for finite trees in L1 (with A. de Mesmay and M. Moharrami) [arxiv]
    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)
  • 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]
    To appear, Combinatorica.
    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]
    Accepted to 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 599S Algorithmic Spectral Graph Theory (Spring'12)
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