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)

teaching:	CSE 521: Design and Analysis of Algorithms
	CSE 599S: Analytical and geometric methods in the theory of computation (Fall 08)

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)
	Sloan Research Fellowship

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)

• On the optimality of gluing over scales (A. Jaffe and M. Moharrami)
  APPROX 2009
• Higher eigenvalues of graphs (with J. Kelner, G. Price, and S-H. Teng)
  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]
  SoCG 2009
• 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) [ps | pdf]
  To appear, Journal of the ACM [ FOCS 2008 ]
• Euclidean sections of L₁ⁿ 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)
  FOCS 2008
• Almost Euclidean subspaces of L₁ⁿ 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]
  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]
• L_p 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 ]

---

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