Arrow Research search

Author name cluster

Bo Brinkman

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers
1 author row

Possible papers

3

STOC Conference 2007 Conference Paper

Vertex cuts, random walks, and dimension reduction in series-parallel graphs

  • Bo Brinkman
  • Adriana Karagiozova
  • James R. Lee

We consider questions about vertex cuts in graphs, random walks in metric spaces, and dimension reduction in L 1 and L 2 ; these topics are intimately connected because they can each be reduced to the existence ofvarious families of real-valued Lipschitz maps on certain metric spaces. We view these issues through the lens of shortest-path metricson series-parallel graphs, and we discussthe implications for a variety of well-known open problems. Our main results follow.

Details

FOCS Conference 2003 Conference Paper

On the Impossibility of Dimension Reduction in l 1

  • Bo Brinkman
  • Moses Charikar

The Johnson-Lindenstrauss Lemma shows that any n points in Euclidean space (with distances measured by the /spl lscr//sub 2/ norm) may be mapped down to O((log n)//spl epsiv//sup 2/) dimensions such that no pairwise distance is distorted by more than a (1+ /spl epsiv/) factor. Determining whether such dimension reduction is possible in /spl lscr//sub 1/ has been an intriguing open question. We show strong lower bounds for general dimension reduction in /spl lscr//sub 1/. We give an explicit family of n points in /spl lscr//sub 1/ such that any embedding with distortion /spl delta/ requires n/sup /spl Omega/(1//spl delta/2)/ dimensions. This proves that there is no analog of the Johnson-Lindenstrauss Lemma for /spl lscr//sub 1/; in fact embedding with any constant distortion requires n/sup /spl Omega/(1)/ dimensions. Further, embedding the points into /spl lscr//sub 1/ with 1 + /spl epsiv/ distortion requires n/sup 1/2 -O(/spl epsiv/log(1//spl epsiv/))/ dimensions. Our proof establishes this lower bound for shortest path metrics of series-parallel graphs. We make extensive use of linear programming and duality in devising our bounds. We expect that the tools and techniques we develop will be useful for future investigations of embeddings into /spl lscr//sub 1/.

Details
v2026.09.13