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.

not a blog: tcsmath (just some expository articles)

Planar multi-flows, L₁ embeddings, and differentiation

The pseudorandom subspace problem

[kernels of random sign matrices | error-correction over the reals]

Eigenvalue multiplicity and growth of groups

travel:
FOCS 2008 (Pittsburgh, PA)
Oct 25-28

MSRI workshop (Berkeley, CA)
Nov 3-7

MIT Appl. Math. Colloquium
Nov 24

U. Chicago theory seminar
Dec 1

teaching: CSE 599S: Analytical and geometric methods in the theory of computation

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

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

BSF grant 2006052 - On some complexity issues between P and NP

(with Arora, Papadimidtriou, Safra)

committees: APPROX 2006, FOCS 2007, SODA 2009

local stuff: [focs'07 hits reading group | UGC/SDP reading group | theory seminar]

Some talks

The virtue of not conforming (eigenvalue bounds)

Expander codes and pseudorandom subspaces of Rⁿ

Nodal domains in random graphs

Algorithms on negatively curved spaces

Trees and Markov convexity

Some strange geometries of computer science

Volume distortion for subsets of Euclidean spaces

Metric embeddings, graph expansion, and high-dimensional convex geometry

Distance scales, embeddings, and efficient relaxations of the cut cone

A brief history of linear programming

Recent papers (2005-present)

Eigenvalue multiplicity and volume growth (with Y. Makarychev) [ps | pdf]
preprint, 2008.

Eigenvalue bounds, spectral partitioning, and metrical deformations via flows (with P. Biswal and S. Rao) [ps | pdf]
To appear, FOCS 2008.

Euclidean sections of L₁ⁿ with sublinear randomness and error-correction over the reals (with V. Guruswami and A. Wigderson) [ps | pdf]
Prelim. version in RANDOM 2008.

Local moves and lossy invariants in planar graph embeddings (with A. Chakrabarti, A. Jaffe, and J. Vincent)
To appear, FOCS 2008.

Almost Euclidean subspaces of L₁ⁿ via expander codes (with V. Guruswami and A. Razborov) [ps | pdf]
Prelim. version in SODA 2008.

Eigenvectors of random graphs: Nodal domains (with Y. Dekel and N. Linial) [ps | pdf]
Prelim. version in RANDOM 2007.

Coarse differentiation and planar multi-flows (with P. Raghavendra) [ps | pdf]
Prelim. version in APPROX 2007.

Vertex cuts, random walks, and dimension reduction in series-parallel graphs (with B. Brinkman and A. Karagiozova)
Prelim. version in STOC 2007.

Trees and Markov convexity (with A. Naor and Y. Peres) [ps | pdf]
To appear, Geometric and Functional Analysis (GAFA). Prelim version in SODA 2006.

Improved distortion bounds for metrics of negative type
in preparation, 2006. [comment]

L_p metrics on the Heisenberg group and the Goemans-Linial conjecture (with A. Naor) [ps | pdf]
Prelim. version in FOCS 2006.

Algorithms on negatively curved spaces (with R. Krauthgamer) [ps | pdf]
Prelim. version in FOCS 2006.

Volume distortion for subsets of Euclidean spaces [ps | pdf]
To appear, Discrete & Computational Geometry. Prelim. version in SoCG 2006.

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. Prelim. version in 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. Prelim. version in STOC 2005.

Distance scales, embeddings, and metrics of negative type [ps | pdf]
(prelim version in SODA 2005)

Unrecent papers

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 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

not a blog:	tcsmath (just some expository articles)
	Planar multi-flows, L₁ embeddings, and differentiation
	The pseudorandom subspace problem
	[kernels of random sign matrices \| error-correction over the reals]
	Eigenvalue multiplicity and growth of groups

travel:	FOCS 2008 (Pittsburgh, PA)	Oct 25-28
	MSRI workshop (Berkeley, CA)	Nov 3-7
	MIT Appl. Math. Colloquium	Nov 24
	U. Chicago theory seminar	Dec 1

funding:	NSF CAREER Award (CCF 0644037) - Geometric phenomena in algorithms and complexity
	BSF grant 2006052 - On some complexity issues between P and NP
	(with Arora, Papadimidtriou, Safra)

old teaching:	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)