Dr. Roy Schwartz of Microsoft Research will speak on "New Approaches to Graph Partitioning."
Graph partitioning problems capture some of the most basic combinatorial optimization problems, and are motivated by a wide range of applications, emerging both in theory and practice. Partitioning problems have been studied extensively in the last few decades, exhibiting beautiful connections to metric geometry, functional analysis, probability theory, and computational complexity.
In this talk we discuss novel techniques to partitioning problems by considering two fundamental examples: Non-Uniform Partitioning and Multiway Cut. For the former we obtain the first provable guarantee, while for the latter we simplify and improve the result of Karger et. al [STOC99]. Our new approaches to these problems employ a combination of combinatorial, stochastic and geometric techniques.
Roy Schwartz is currently a post-doctoral researcher at the Theory Group at Microsoft Research. He completed his Ph.D. at the Technion under the supervision of Prof. Seffi Naor. His main research interests include the design and analysis of algorithms, combinatorial optimization, submodular optimization, metric methods and their applications, approximation algorithms, and randomized algorithms. Roy's work deals both with fundamental algorithmic problems as well as applications that arise in other settings such as networking, game theory, and scheduling.
Events are free and open to the public unless otherwise noted.