| Title: | Lower Bounds for Additive Spanners, Emulators, and More |
| Date: |
August 14, 2006 (Monday)
|
| Time: |
11:00 a.m. - 12:00 noon
|
| Venue: |
Room 121, 1/F, Ho Sin-hang Engineering Building,
The Chinese University of Hong Kong, Shatin, N.T. |
| Speaker: |
Mr. David Woodruff
PhD candidate Department of Computer Science Massachusetts Institute of Technology USA |
An additive spanner of an unweighted undirected graph G with distortion d is a subgraph H such that for any two vertices u,v in G, we have delta_H(u,v) <= delta_G(u,v) + d, where delta_G(u,v) denotes the shortest-path distance from u to v in G. For every k = O(ln n / ln ln n), we construct a graph G on n vertices for which any additive spanner of G with distortion 2k-1 has Omega (n^{1+1/k}/k) edges. This matches the lower bound previously known only to hold under a 1963 conjecture of Erdos.
We generalize our lower bound technique in a number of ways. First, we consider graph emulators introduced by Dor, Halperin, and Zwick (FOCS, 1996), where an emulator of an unweighted undirected graph G with distortion d is like an additive spanner except H may be an arbitrary weighted graph such that delta_G(u,v) <= delta_H(u,v) <= delta_G(u,v) + d. We show a lower bound of Omega (n^{1+1/k}/k2) edges for distortion-(2k-1) emulators. These are the first non-trivial bounds for k > 3. Second, we parameterize our bounds in terms of the minimum degree d of the graph. This partially answers a question of Baswana el al (SODA, 2005) for additive spanners, and our bounds are tight for distortion 2 spanners and distortion 4 emulators. Finally, we continue the study of pair-wise and source-wise distance preservers defined by Coppersmith and Elkin (SODA, 2005) by considering their approximate variants and their relaxation to emulators. We prove the first lower bounds for such graphs.
Work to appear in FOCS, 2006.
BIOGRAPHY:
David Woodruff is a fourth-year Ph.D. student in the MIT theoretical computer science group. In 2002 he received a Master's degree in computer science, a B.S. degree in computer science, and a B.S. degree in mathematics, all from MIT. He is spending the 2005-2006 academic year as a visiting student at Tsinghua University.
David's research interests include algorithms, communication complexity, and cryptography. Many of his papers focus on (1) reducing the communication complexity for cryptographic tasks, (2) upper and lower bound techniques for streaming problems, and (3) faster algorithms for problems occurring in broadcast encryption, computational biology, and datamining. He is also very interested in algebra, combinatorics, and graph theory. On a practical side, some of his work has resulted in several patents at PARC and DoCoMo Labs.
Enquiries: Miss Temmy So at tel 2609 8444
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar