funk

James R. Lee

Associate Professor
Department of Computer Science and Engineering
University of Washington
(contact info at bottom)

email: jrl @ cs (dot) washington (dot) edu

Ph.D., Computer Science, U. C. Berkeley, 2005
Postdoc, Institute for Advanced Study, Princeton, 2005-2006

Research interests:
Algorithms and complexity theory. Geometry and analysis at the interface between the continuous and discrete. Probability, spectral graph theory, and metric geometry.

(not a) blog: tcsmath

recent program committees: SODA 2014, ICALP 2014, FOCS 2014.

recent papers in spectral graph theory/probability/statistics

Regularization under diffusion and anti-concentration of temperature, with R. Eldan
A Gaussian upper bound for martingale small-ball probabilities, with Y. Peres and C. K. Smart
Adversarial hypothesis testing and a quantum Stein's Lemma for restricted measurements,with F. G. S. L. Brandao, A. W. Harrow, and Y. Peres (Annals of Statistics)
Multi-way spectral partitioning and higher-order Cheeger inequalities, with S. Oveis Gharan and L. Trevisan (STOC'12, JACM)
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 approximation algorithms/embeddings/metric geometry

On the power of symmetric LP and SDP relaxations, with P. Raghavendra, D. Steurer, and N. Tan (CCC'14)
Approximate constraint satisfaction requires large LP relaxations, with S. Chan, P. Raghavendra, and D. Steurer (FOCS'13)
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, Math. Prog.)
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, DCG)
    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, notes, and manuscripts

  • On the power of symmetric LP and SDP relaxations (with P. Raghavendra, D. Steurer, and N. Tan)
    CCC 2014.
  • Approximate constraint satisfaction requires large LP relaxations (with S. Chan, P. Raghavendra, and D. Steurer) [arxiv]
    FOCS 2013.
  • Adversarial hypothesis testing and a quantum Stein's Lemma for restricted measurements (with F. G. S. L. Brandao, A. W. Harrow, and Y. Peres) [arxiv]
    ITCS 2014.

  • A lower bound on dimension reduction for trees in L1 (with M. Moharrami) [arxiv]
  • On the 2-sum embedding conjecture (with D. Poore)
    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]
    STOC 2013.
  • Markov type and threshold embeddings (with J. Ding and Y. Peres) [arxiv]
    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]
    To appear, Journal of the ACM. [ 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]
    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]
    Annals of Probability.
  • On the optimality of gluing over scales (with A. Jaffe and M. Moharrami) [arxiv]
    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]
    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