Approximating Spanners via Convex Relaxations

Michael Dinitz, Weizmann Institute of Science
Host: Vladimir Braverman

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

Michael 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.