All reports by Author James R. Lee:

__
TR08-060
| 10th April 2008
__

James R. Lee, Prasad Raghavendra#### Coarse Differentiation and Multi-flows in Planar Graphs

__
TR07-086
| 7th September 2007
__

Venkatesan Guruswami, James R. Lee, Alexander Razborov#### Almost Euclidean subspaces of $\ell_1^N$ via expander codes

James R. Lee, Prasad Raghavendra

We show that the multi-commodity max-flow/min-cut gap for series-parallel graphs can be as bad as 2, matching a recent upper bound by Chakrabarti.et.al for this class, and resolving one side of a conjecture of Gupta, Newman, Rabinovich, and Sinclair.

This also improves the largest known gap for planar graphs ... more >>>

Venkatesan Guruswami, James R. Lee, Alexander Razborov

We give an explicit (in particular, deterministic polynomial time)

construction of subspaces $X

\subseteq \R^N$ of dimension $(1-o(1))N$ such that for every $x \in X$,

$$(\log N)^{-O(\log\log\log N)} \sqrt{N}\, \|x\|_2 \leq \|x\|_1 \leq \sqrt{N}\, \|x\|_2.$$

If we are allowed to use $N^{1/\log\log N}\leq N^{o(1)}$ random bits

and ...
more >>>