

2013/02/26, MC437, 10:00  11:00
Large and complicated data sets have become ubiquitous in science and engineering, and have given rise to new challenges in Computer Science. In this new computational horizon, geometry has become an indispensable source of algorithmic tools, and ideas. A main catalyst behind this development has been the theory of metric embeddings. A metric embedding is a mapping from a metric space X into some metric space Y, which preserves all pairwise distances up to a small factor, called the distortion.
In this talk I will describe a general framework for obtaining lowdistortion embeddings of complicated spaces into simpler ones. An immediate corollary is a general reduction from hard instances to corresponding simpler ones, for a large class of optimization problems on certain families of graphs. Moreover, these techniques yield improvements on the state of the art for problems such as Sparsest Cut, Treewidth, Crossing Number, Vertex Sparsification, 0Extension, and the estimation of Laplacian eigenvalues for several interesting graph families.
Perhaps surprisingly, the above ideas can also be used to construct hard instances for certain problems. More precisely, guided by the above simplification machinery, we construct spaces that yield a nearly optimal integrality gap for a specific SDP relaxation of Sparsest Cut.
Dr. Sidiropoulos received his M.S. and Ph.D. in Electrical Engineering and Computer Science at the Massachusetts Institute of Technology, under the supervision of Piotr Indyk. He has been a postdoctoral fellow at the University of Toronto, and the Toyota Technological Institute at Chicago. He is currently a postdoctoral fellow in the Computer Science department at the University of Illinois at UrbanaChampaign.
His main research interests are in algorithms, with an emphasis on metric embeddings, highdimensional and lowdimensional computational geometry, graph theory, optimization, and applications of geometry and topology in computer science.


