[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

The University of Chicago Computer Science Department
 
 THEORY SEMINAR
 
 Friday, May 30, 2014
3:00 p.m.
Ryerson 251
 
Aleksander Madry
Ecole Polytechnique Federale De Lausanne
thl.epfl.ch/madry/
 
 
Title: “Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back”
 
Abstract: We describe a new way of employing electrical flow computations to solve the maximum flow and minimum s-t cut problems. This approach draws on ideas underlying path-following interior-point methods (IPMs) – a powerful tool in convex optimization - and exploits certain interplay between maximum flows and bipartite matchings.
 
The resulting algorithm provides improvements over some long-standing running time bounds for the maximum flow and minimum  s-t cut problems, as well as, the closely related bipartite matching problem. Additionally, we establish a connection between primal-dual structure of electrical flows and convergence behavior of IPMs when applied to flow problems. This connection enables us to overcome the notorious Omega(sqrt(m))-iterations convergence barrier that all the known interior-point methods suffer from.
 
 
Hosts: Prof. Janos Simon
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
 



















































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































*REMINDER*

THEORY SEMINAR

Tuesday, May 6, 2014
3:00 p.m.
Ryerson 251

Nick Harvey
University of British Columbia
www.cs.ubc.ca/~nickhar

Title: "Spectrally Thin Trees"

Abstract:
Thin trees are intriguing objects in graph theory that relate to
foundational topics, such as nowhere-zero flows and the asymmetric
traveling salesman problem (ATSP). A spanning subtree T of a graph G
is called alpha-thin if every cut in T contains at most an
alpha-fraction of G's edges in that cut.

Asadpour et al gave an algorithm constructing an
O(log n / k log log n)-thin tree in any graph with n vertices and
edge-connectivity k. Improving this to O(1/k) would imply a
constant-factor approximation algorithm for ATSP.

We define a stronger notion of thinness that is naturally motivated by
spectral sparsification of graphs. A spanning subtree T of G is called
alpha-spectrally-thin if T's Laplacian matrix is upper-bounded by
alpha times G's Laplacian matrix in the Lowner ordering.

We give a deterministic, polynomial time algorithm to construct an
O(log n / c log log n)-spectrally thin tree in any graph with n vertices
and for which the effective conductance across each edge is at least c.

Remarkably, this can be improved to O(1/c) if one does not require
an efficient algorithm. The recent breakthrough results of Marcus, Spielman
and Srivastava imply the existence of a O(1/c)-spectrally-thin tree.

This is joint work with Neil Olver (MIT / Vrije Universiteit). 

Host: Prof. Alexander Razborov
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*




-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20140527/8928f492/attachment.htm