Skip to content. Skip to navigation
McGill Home SOCS Home
Personal tools
You are here: Home Announcements and Events Seminars profile

Seminars
Fall 2014 Schedule
Winter 2015 Schedule
Archive


         
     
 
2013/02/26, MC437, 10:00 - 11:00


Anastasios Sidiropoulos , CS department at the University of Illinois at Urbana-Champaign.

Abstract:

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 low-distortion 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, 0-Extension, 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.

Biography of Speaker:

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 post-doctoral fellow at the University of Toronto, and the Toyota Technological Institute at Chicago. He is currently a post-doctoral fellow in the Computer Science department at the University of Illinois at Urbana-Champaign. His main research interests are in algorithms, with an emphasis on metric embeddings, high-dimensional and low-dimensional computational geometry, graph theory, optimization, and applications of geometry and topology in computer science.