Approximating Spanners via Convex Relaxations
Thursday, March 14, 2013 - 8:30am - 9:45am
KEC 1005
Dr. Michael Dinitz
Postdoctoral Fellow
Faculty of Mathematics and Computer Science
Weizmann Institute of Science
Abstract:
Many optimization problems in networking and distributed computing have been
approached with only combinatorial techniques, despite the prevalence of
mathematical programming in modern approximation algorithms. In this talk I
will discuss new algorithms for some problems in network design, namely graph
spanners, that use advanced convex relaxation-based techniques rather than the
traditional combinatorial approaches.
Graph spanners are subgraphs that approximately preserve distances between
nodes, and are a fundamental building block in distributed computing in
addition to being useful in areas as diverse as efficiently solving linear
systems and property testing of functions. Our new techniques have allowed us
to solve fundamental algorithmic problems on spanners that have been open for
almost 20 years.
I will also demonstrate the broader relevance of our techniques, including to
more applied problems such as designing good overlays for autonomous systems
running the Interior Border Gateway Protocol (IBGP). Finally, I will discuss
some recent progress on complexity-theoretic lower bounds for approximating
similar problems, based on new constructions of probabilistically-checkable
proofs.
Speaker Biography:
Dr. Dinitz received his A.B. in computer science from Princeton University, with a certificate in applied and computational mathematics. He received his Ph.D. in computer science from Carnegie Mellon University, where he was advised by Anupam Gupta. Since then he has been a postdoctoral fellow in the Faculty of Mathematics and Computer Science at the Weizmann Institute of Science in Israel, where he is hosted by Robert Krauthgamer and David Peleg. He is broadly interested in algorithms, with a particular focus on approximation algorithms for problems inspired by networking and distributed computing.
_______________________________________________
Colloquium mailing list
[email protected]
https://secure.engr.oregonstate.edu/mailman/listinfo/colloquium
