Seminars and Colloquia by Series

Thursday, September 21, 2017 - 13:30 , Location: Skiles 005 , Laszlo Vegh , London School of Economics , L.Vegh@lse.ac.uk , Organizer: Prasad Tetali
We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation.Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem.This is joint work with Ola Svensson and Jakub Tarnawski.
Monday, April 18, 2016 - 15:05 , Location: Skiles 006 , Annie Raymond , University of Washington, Seattle, WA , raymonda@uw.edu , Organizer: Prasad Tetali
Given a graph H, the Turan graph problem asks to find the maximum number of edges in a n-vertex graph that does not contain any subgraph isomorphic to H. In recent years, Razborov's flag algebra methods have been applied to Turan hypergraph problems with great success. We show that these techniques embed naturally in standard symmetry-reduction methods for sum of squares representations of invariant polynomials.  This connection gives an alternate computational framework for Turan problems with the potential to go further. Our results expose the rich combinatorics coming from the representation theory of the symmetric group present in flag algebra methods. This is joint work with James Saunderson, Mohit Singh and Rekha Thomas.
Friday, November 13, 2015 - 15:05 , Location: Skiles 005 , Noga Alon , Tel Aviv University and IAS, Princeton , Organizer: Robin Thomas

Refreshments will be served in the atrium after the talk.

The sign-rank of a real matrix A with no 0 entries is the minimum rank of a matrix B so that A_{ij}B_{ij} >0 for all i,j. The study of this notion combines combinatorial, algebraic, geometric and probabilistic techniques with tools from real algebraic geometry, and is related to questions in Communication Complexity, Computational Learning and Asymptotic Enumeration. I will discuss the topic and describe its background, several recent results from joint work with Moran and Yehudayoff, and some intriguing open problems.
Friday, August 21, 2015 - 15:05 , Location: Skiles 006 , Paul Wollan , University of Rome "La Sapienza" , Organizer: Robin Thomas

Refreshments will be served in the atrium immediately following the talk. Please join us to welcome the new class of ACO students.

Graph immersion is an alternate model for graph containment similar to graph minors or topological minors. The presence of a large clique immersion in a graph G is closely related to the edge connectivity of G. This relationship gives rise to an easy theorem describing the structure of graphs excluding a fixed clique immersion which serves as the starting point for a broader structural theory of excluded immersions. We present the highlights of this theory with a look towards a conjecture of Nash-Williams on the well-quasi-ordering of graphs under strong immersions and a conjecture relating the chromatic number of a graph and the exclusion of a clique immersion.
Thursday, March 27, 2014 - 15:00 , Location: Skiles 268 , Ilan Adler , University of California, Berkeley , Organizer: Robin Thomas
It is well known that many optimization problems, ranging from linear programming to hard combinatorial problems, as well as many engineering and economics problems, can be formulated as linear complementarity problems (LCP).  One particular problem, finding a Nash equilibrium of a bimatrix game (2 NASH), which can be formulated as LCP, motivated the elegant Lemke algorithm to solve LCPs. While the algorithm always terminates, it can generates either a solution or a so-called ‘secondary ray’. We say that the algorithm resolves a given LCP if a secondary ray can be used to certify, in polynomial time, that no solution exists. It turned out that in general, Lemke-resolvable LCPs belong to the complexity class PPAD and that, quite surprisingly, 2 NASH is PPAD-complete. Thus, Lemke-resolvable LCPs can be formulated as 2 NASH. However, the known formulation (which is designed for any PPAD problem) is very complicated, difficult to implement, and not readily available for potential insights. In this talk, I’ll present and discuss a simple reduction of Lemke-resolvable LCPs to bimatrix games that is easy to implement and have the potential to gain additional insights to problems (including several models of market equilibrium) for which the reduction is applicable.
Thursday, January 9, 2014 - 16:30 , Location: Skiles 005 , Leonard J. Schulman , Professor, CalTech , Organizer: Prasad Tetali
Tree codes are the basic underlying combinatorial object in the interactive coding theorem, much as block error-correcting codes are the underlying object in one-way communication. However, even after two decades, effective (poly-time) constructions of tree codes are not known. In this work we propose a new conjecture on some exponential sums. These particular sums have not apparently previously been considered in the analytic number theory literature. Subject to the conjecture we obtain the first effective construction of asymptotically good tree codes. The available numerical evidence is consistent with the conjecture and is sufficient to certify codes for significant-length communications. (Joint work with Cris Moore.)
Friday, December 6, 2013 - 15:05 , Location: Skiles 005 , Adam Marcus , Crisply.com and Yale Unversity , Organizer: Prasad Tetali
 We will outline the proof that gives a positive solution to Weaver's conjecture $KS_2$.  That is, we will show that any isotropic collection of vectors whose outer products sum to twice the identity can be partitioned into two parts such that each part is a small distance from the identity. The distance will depend on the maximum length of the vectors in the collection but not the dimension (the two requirements necessary for Weaver's reduction to a solution of Kadison--Singer).  This will include introducing a new technique for establishing the existence of certain combinatorial objects that we call the "Method of Interlacing Polynomials." This talk is intended to be accessible by a general mathematics audience, and represents joint work with Dan Spielman and Nikhil Srivastava.
Wednesday, February 15, 2012 - 16:30 , Location: Skiles 005 , Andrew Goldberg , Principal Researcher, Microsoft Research Silicon Valley, CA , Organizer: Prasad Tetali

(Refreshments in the lounge outside Skiles 005 at 4:05pm)

This is a survey of Hub Labeling results for general and road networks.Given a weighted graph, a distance oracle takes as an input a pair of vertices and returns the distance between them. The labeling approach to distance oracle design is to precompute a label for every vertex so that distances can be computed from the corresponding labels. This approach has been introduced by [Gavoille et al. '01], who also introduced the Hub Labeling algorithm (HL). HL has been further studied by [Cohen et al. '02].We study HL in the context of graphs with small highway dimension (e.g., road networks). We show that under this assumption HL labels are small and the queries are sublinear. We also give an approximation algorithm for computing small HL labels that uses the fact that shortest path set systems have small VC-dimension.Although polynomial-time, precomputation given by theory is too slow for continental-size road networks. However, heuristics guided by the theory are fast, and compute very small labels. This leads to the fastest currently known practical distance oracles for road networks.The simplicity of HL queries allows their implementation inside of a relational database (e.g., in SQL), and query efficiency assures real-time response. Furthermore, including HL data in the database allows efficient implementation of more sophisticated location-based queries. These queries can be combined with traditional SQL queries. This approach brings the power of location-based services to SQL programmers, and benefits from external memory implementation and query optimization provided by the underlying database.Joint work with Ittai Abraham, Daniel Delling, Amos Fiat, and Renato Werneck.
Tuesday, October 11, 2011 - 11:00 , Location: Skiles 006 , David P. Williamson , Cornell University and TU Berlin , dpw@cs.cornell.edu , Organizer: Prasad Tetali

Refreshments at 10:30am in the atrium outside Skiles 006

The traveling salesman problem (TSP) is the most famous problem in discrete optimization.  Given $n$ cities and   the costs $c_{ij}$ for traveling from city $i$ to city $j$ for all $i,j$, the goal of the problem is to find the least expensive tour that visits each city exactly once and returns to its starting point.  We consider cases in which the costs are symmetric and obey the triangle inequality.  In 1954, Dantzig, Fulkerson, and Johnson introduced a linear programming relaxation of the TSP now known as the subtour LP, and used it to find the optimal solution to a 48-city instance.  Ever since then, the subtour LP has been used extensively to find optimal solutions to TSP instances, and it is known to give extremely good lower bounds on the length of an optimal tour. Nevertheless, the quality of the subtour LP bound is poorly understood from a theoretical point of view.  For 30 years it has been known that it is at least 2/3 times the length of an optimal tour for all instances of the problem, and it is known that there are instances such that it is at most 3/4 times the length of an optimal tour, but no progress has been made in 30 years in tightening these bounds. In this talk we will review some of the results that are known about the subtour LP, and give some new results that refine our understanding in some cases.  In particular, we resolve a conjecture of Boyd and Carr about the ratio of an optimal 2-matching to the subtour LP bound in the worst case.  We also begin a study of the subtour LP bound for the extremely simple case in which all costs $c_{ij}$ are either 1 or 2.  For these instances we can show that the subtour LP is always strictly better than 3/4 times the length of an optimal tour. These results are joint work with Jiawei Qian, Frans Schalekamp, and Anke van Zuylen.
Thursday, March 3, 2011 - 16:30 , Location: Skiles 006 , Alon Orlitsky , Professor, UCSD , alon@ucsd.edu , Organizer: Prasad Tetali
Motivated by mass-spectrometry protein sequencing, we consider the simple problem of reconstructing a string from its substring compositions. Relating the question to the long-standing turnpike problem, polynomial factorization, and cyclotomic polynomials, we cleanly characterize the lengths of reconstructable strings and the structure of non-reconstructable ones. The talk is elementary and self contained and covers work with Jayadev Acharya, Hirakendu Das, Olgica Milenkovic, and Shengjun Pan.

Pages