Seminars and Colloquia by Series

Friday, April 12, 2019 - 15:05 , Location: Skiles 005 , Cynthia Vinzant , North Carolina State University, Raleigh, NC , Organizer: Prasad Tetali

Stability is a multivariate generalization for real-rootedness in univariate polynomials. Within the past ten years, the theory of stable polynomials has contributed to breakthroughs in combinatorics, convex optimization, and operator theory. I will introduce a generalization of stability, called complete log-concavity, that satisfies many of the same desirable properties. These polynomials were inspired by work of Adiprasito, Huh, and Katz on combinatorial Hodge theory, but can be defined and understood in elementary terms. The structure of these polynomials is closely tied with notions of discrete convexity, including matroids, submodular functions, and generalized permutohedra. I will discuss the beautiful real and combinatorial geometry underlying these polynomials and applications to matroid theory, including a proof of Mason’s conjecture on numbers of independent sets. This is based on joint work with Nima Anari, Kuikui Liu, and Shayan Oveis Gharan.

(*Refreshments available at 2:30pm before the colloquium.*)

Tuesday, February 27, 2018 - 11:00 , Location: Skiles 006 , Alexander Barvinok , University of Michigan , , Organizer: Prasad Tetali
Many hard problems of combinatorial counting can be encoded as problems
of computing an appropriate partition function. Formally speaking, such a
partition function is just a multivariate polynomial with great many
monomials enumerating combinatorial structures of interest. For example,
the permanent of an nxn matrix is a polynomial of degree n in n^2
variables with n! monomials enumerating perfect matchings in the
complete bipartite graph on n+n vertices. Typically, we are interested
to compute the value of such a polynomial at a real point; it turns out
that to do it efficiently, it is very helpful to understand the behavior
of complex zeros of the polynomial. This approach goes back to the
Lee-Yang theory of the critical temperature and phase transition in
statistical physics, but it is not identical to it: thinking of the
phase transition from the algorithmic point of view allows us greater
flexibility: roughly speaking, for computational purposes we can freely
operate with “complex temperatures”.

I plan to illustrate this approach on the problems of computing the
permanent and its versions for non-bipartite graphs (hafnian) and
hypergraphs, as well as for computing the graph homomorphism partition
function and its versions (partition functions with multiplicities and
tensor networks) that are responsible for a variety of problems on
graphs involving colorings, independent sets, Hamiltonian cycles, etc. (This is the first (overview) lecture; two more will follow up on Thursday 1:30pm, Friday 3pm of the week. These two lectures are each 80 minutes' long.)

Thursday, September 21, 2017 - 13:30 , Location: Skiles 005 , Laszlo Vegh , London School of Economics , , 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 , , 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 &amp;quot;La Sapienza&amp;quot; , 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
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 , , 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.