|
|
|
James
R. Lee
email: jrl @ cs dot
(obvious)
Assistant 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.
Applications
of geometry and analysis in theoretical computer science.
I am organizing the theory
seminar.
|
| not a blog: |
tcsmath (just some expository
articles) |
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.
old reading groups:
[focs'07
hits reading group | UGC/SDP reading
group]
Some talks
Recent papers (2006-present)
- Bilipschitz snowflakes, metrics of negative type, and PSD flows (with M. Moharrami)
To appear, 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]
Manuscript.
- On the optimality of gluing over scales (with A. Jaffe and M. Moharrami)
[arxiv]
APPROX 2009
- Higher eigenvalues of graphs
(with J. Kelner, G. Price, and S.-H. Teng)
[ps
| pdf]
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)
[ps
| pdf]
To appear, special issue of Computational Geometry, Theory and Applications [ 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)
STOC 2009
- Eigenvalue multiplicity and volume growth
(with Y. Makarychev)
[ps
| pdf]
submitted, 2008.
- Eigenvalue bounds, spectral partitioning, and metrical
deformations via flows
(with P. Biswal and S. Rao)
[arxiv]
To appear, Journal of the ACM [
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]
To appear, Combinatorica [
SODA
2008 ]
- Eigenvectors of random graphs: Nodal domains
(with Y. Dekel
and N. Linial)
[ps |
pdf]
To appear, Random Strucures & Algorithms
[ RANDOM
2007 ]
- Coarse differentiation and planar multi-flows
(with P. Raghavendra)
[ps
| pdf]
To appear, Discrete & Computational Geometry [ APPROX
2007 ]
- Vertex cuts, random walks, and dimension reduction in
series-parallel graphs (with B. Brinkman and A. Karagiozova)
STOC 2007
- Trees and Markov convexity (with A. Naor and Y.
Peres)
[ps
| pdf]
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 ]
Unrecent papers
- Frechet embeddings of negative type metrics.
(with S. Arora and A. Naor)
[ps
| pdf]
Discrete
& Computational Geometry, 38(4): 726-739, 2007.
- An improved approximation ratio for the minimum linear
arrangement
problem (with U. Feige) [ps
| pdf]
Information Processing
Letters, 101(1): 26-29, 2007.
- Euclidean distortion and the Sparsest Cut
(with S. Arora and A. Naor)
[ps
| pdf]
Journal of the American
Mathematical Society, 21(1): 1-21, 2008.
[ STOC 2005 ]
- Improved approximation algorithms for minimum-weight
vertex separators.
(with U. Feige and M. T. Hajiaghayi)
[ps
| pdf]
SIAM
Journal on Computing, 38(2): 629-657, 2008.
[ STOC 2005 ]
- Distance scales, embeddings, and metrics of negative type
[ps
| pdf]
(prelim version in SODA 2005)
- Measured descent: A new embedding method for finite
metrics.
(with Robert Krauthgamer, Manor Mendel, and Assaf Naor)
Geometric
and Functional Analysis (GAFA), 15(4): 839-858, 2005.
Prelim. version in FOCS 2004
(Rome, Italy).
[preprint: pdf]
- The black-box complexity of nearest neighbor search.
(with Robert Krauthgamer)
Special (ICALP'04) issue of Theoretical
Computer Science 348(2): 129-366, 2005.
Prelim. version in ICALP 2004
(Turku, Finland).
[preprint: ps
| pdf]
- Navigating nets: Simple algorithms for proximity
search.
(with Robert Krauthgamer)
Proceedings of SODA 2004
(New Orleans, LA).
[conf. version: ps
| pdf]
- Absolute Lipschitz extendability.
(with Assaf Naor)
Comptes
Rendus de l'Acadèmie
des Sciences - Series I - Mathematics, 338(11): 859-862, 2004.
- Extending Lipschitz functions via random metric
partitions.
(with Assaf Naor)
Math.
Invent., 160(1): 59-95, 2005.
[preprint: ps
| pdf]
- Metric structures in L1:
Dimension, snowflakes,
and average distortion.
(with Manor Mendel and Assaf Naor)
European
Journal of Combinatorics,
26(8): 1180-1190, 2005.
[preprint: ps
| pdf]
- Embedding the diamond graph in Lp
and dimension
reduction in L1.
(with Assaf Naor)
Geometric
and Functional Analysis (GAFA), 14(4): 745-747, 2004.
[ps
| pdf]
- Bounded geometries, fractals, and low-distortion
embeddings.
(with Anupam Gupta and Robert Krauthgamer)
Prelim. version in FOCS
2003 (Cambridge, MA).
[conf. version: ps
| pdf]
- The intrinsic dimensionality of graphs.
(with Robert Krauthgamer)
Combinatorica,
27(5): 551-585, 2007.
Prelim. version in STOC 2003 (San
Diego, CA).
[full version: ps | pdf]
- Hardness
of approximating vertex-connectivity
network design problems.
(with Guy Kortsarz and Robert Krauthgamer)
SIAM
Journal on Computing,
33(3):704-720, 2004.
Prelim. version in APPROX 2002 (Rome, Italy).
[ps
| pdf]
happiness is a warm theorem.
| old teaching: |
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
