## Seminars and Colloquia by Series

Series
ACO Colloquium
Time
Friday, December 6, 2013 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
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.

### The Hub Labeling Algorithm

Series
ACO Colloquium
Time
Wednesday, February 15, 2012 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Andrew GoldbergPrincipal Researcher, Microsoft Research Silicon Valley, CA

Please Note: (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.

### The Subtour LP for the Traveling Salesman Problem

Series
ACO Colloquium
Time
Tuesday, October 11, 2011 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
David P. WilliamsonCornell University and TU Berlin

Please Note: 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.

### String Reconstruction from Substring Compositions

Series
ACO Colloquium
Time
Thursday, March 3, 2011 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Alon Orlitsky Professor, UCSD
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.

### Forbidden paths

Series
ACO Colloquium
Time
Thursday, March 18, 2010 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Jaroslav NesetrilCharles University, Prague

Please Note: ***Refreshments at 4PM in Skiles 236.***

Forbidding (undirected or directed) paths in graphs, what can be easier? Yet we show that in the context of coloring problems (CSP) and structural graph theory, this is related to the notions tree depth, (restricted) dualities, bounded expansion and nowhere dense classes with applications both in and out of combinatorics.

### A combinatorial approach to the interpolation method and scaling limits in sparse random graphs

Series
ACO Colloquium
Time
Wednesday, February 17, 2010 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 255 (Refreshments at 4pm in Skiles 236)
Speaker
David GamarnikProfessor, M.I.T.
We establish the existence of scaling limits for several combinatorial optimization models on Erdos-Renyi and sparse random regular graphs. For a variety of models, including maximum independent sets, MAX-CUT, coloring and K-SAT, we prove that the optimal value appropriately rescaled, converges to a limit with high probability (w.h.p.), as the size of the underlying graph divergesto infinity. For example, as a special case we prove that the size of a largest independent set in these graphs, normalized by the number of nodes converges to a limit w.h.p. thus resolving an open problem. Our approach is based on developing a simple combinatorial approach to an interpolation method developed recently in the statistical physics literature. Among other things, theinterpolation method was used to prove the existence of the so-called free energy limits for several spin glass models including Viana-Bray and random K-SAT models. Our simpler combinatorial approach allows us to work with the zero temperature case (optimization) directly and extend the approach to many other models. Additionally, using our approach, we establish the large deviationsprinciple for the satisfiability property for constraint satisfaction problems such as coloring, K-SAT and NAE(Not-All-Equal)-K-SAT. The talk will be completely self-contained. No background on random graph theory/statistical physics is necessary. Joint work with Mohsen Bayati and Prasad Tetali

### In search of a thin tree - new approximation algorithms for the asymmetric traveling salesman problem

Series
ACO Colloquium
Time
Thursday, January 14, 2010 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Amin SaberiStanford University

Please Note: Refreshments at 4:00PM in Skiles 236

I will talk about new approximation algorithms for the Asymmetric Traveling Salesman Problem (ATSP) when the costs satisfy the triangle inequality. Our approach is based on constructing a "thin" spanning tree from the solution of a classical linear programming relaxation of the problem and augmenting the tree to an Eulerian subgraph. I will talk about Goddyn's conjecture on the existence of such trees and its relations to nowhere-zero flows. I will present an O(log n/log log n) approximation algorithm that uses a new randomized rounding method. Our rounding method is based on sampling from a distribution and could be of independent interest. Also, I will talk about the special case where the underlying undirected graph of the LP relaxation of the problem has bounded genus. This is the case for example, when the distance functions are shortest paths in a city with few bridges and underpasses. We give a constant factor approximation algorithm in that case. The first result is a joint work with A. Asadpour, M. Goemans, A. Madry and S. Oveis Gharan, and the second result is a joint work with S. Oveis Gharan.

### Extremal graph theory and related areas

Series
ACO Colloquium
Time
Thursday, November 12, 2009 - 16:30 for 2 hours
Location
Skiles 255
Speaker
Miklos SimonovitsAlfred Renyi Institute, Budapest, Hungary
In my talk I will give a survey on the rise and early development of Extremal Graph Theory, one of the large areas in Discrete Mathematics.I will give a description of the asymptotic solution of extremal graph problems for ordinary graphs, describe the stability method and expose the difficulties connected to hypergraph extremal problems.I will expose several unsolved problems in the field, and move on to some new results.I will also describe the connection of the field to several other areas of Discrete Mathematics, like to Ramsey Theory,Random graphs, Regularity lemma, Quasi-randomness, etc.I will also mention some applications of extremal graph theory. The lecture will be a non-technical one.***Refreshments at 4PM in Skiles 236.***

### CANCELLED -- Sparse matrices, sparse signals, and sparse algorithms

Series
ACO Colloquium
Time
Tuesday, April 21, 2009 - 16:30 for 2 hours
Location
Skiles 255
Speaker
Anna GilbertUniversity of Michigan, Ann Arbor
The past 10 years have seen a confluence of research in sparse approximation amongst computer science, mathematics, and electrical engineering. Sparse approximation encompasses a large number of mathematical, algorithmic, and signal processing problems which all attempt to balance the size of a (linear) representation of data and the fidelity of that representation. I will discuss several of the basic algorithmic problems and their solutions, focusing on special classes of matrices. I will conclude with an application in biological testing.

### The Linear Complementarity Problem, Lemke Algorithm, Perturbation, and the Complexity Class PPAD

Series
ACO Colloquium
Time
Wednesday, April 1, 2009 - 16:30 for 2 hours
Location
Klaus 1116E
Speaker