I dabble in mixed martial arts

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. Applications of geometry and analysis in theoretical computer science.

not a blog:	tcsmath (just some expository articles)
	Planar multi-flows, L1 embeddings, and differentiation
	The pseudorandom subspace problem

teaching:

CSE 431 Introduction to the Theory of Computation (Spring '08)

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

• 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 bounds, spectral partitioning, and metrical deformations via flows (with P. Biswal and S. Rao)
  submitted, 2008.
• Euclidean sections of L₁ⁿ with sublinear randomness and error-correction over the reals (with V. Guruswami and A. Wigderson)
  submitted, 2008.
• Local moves and lossy invariants in planar graph embeddings (with A. Chakrabarti, A. Jaffe, and J. Vincent)
  submitted, 2007.
• Almost Euclidean subspaces of L₁ⁿ via expander codes (with V. Guruswami and A. Razborov) [ps | pdf]
  To appear, SODA 2008.
• Eigenvectors of random graphs: Nodal domains (with Y. Dekel and N. Linial)
  To appear, 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]
  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]
  To appear, SIAM Journal on Computing. 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 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