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

Seminar Home
Fall 2014 Schedule
Winter 2015 Schedule
Summer 2015 Schedule
Archives

SOCS Theory Seminar Schedule

Date Category Seminar Info
2013/03/27 Theory Place: MC 437
Time: 10:00 - 11:00
Speaker: Vida Dujmovic
Affiliation: Assistant Professor, Carleton University, School of Mathematics and Statistics & Department of Syste
Area: Theory
Title: Graph Layouts
Abstract:

A 3D grid drawing of a graph is a placement of the vertices at distinct gridpoints in 3D such that the straight line-segments representing the edges are pairwise non-crossing. 3D grid drawings of small volume are closely related to a graph parameter called queue number. I will present the state of the art on the topic focusing on the most recent result that planar graphs have O(n log n) volume 3D grid drawings and O(log n) queue number. This improves the result by Di Battista, Frati and Pach [FOCS’10, pp. 365–374].

Biography of Speaker:

Vida Dujmovic is an Assistant Professor at the School of Mathematics and Statistics & Department of Systems and Computer Engineering of Carleton University. She has obtained her PhD and MSc from McGill University and her BEng from University of Zagreb in Croatia. She is a recipient of NSERC Doctoral Prize and, more recently, Faculty Research Achievement Award of Carleton University.


2013/02/26 Theory Place: MC437
Time: 10:00 - 11:00
Speaker: Anastasios Sidiropoulos
Affiliation: CS department at the University of Illinois at Urbana-Champaign.
Title:
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.