- You are here:
- GT Home
- Home
- News & Events

Series: ACO Colloquium

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.*)

Series: ACO Colloquium

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”.

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.)

Series: ACO Colloquium

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.

Series: ACO Colloquium

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.

Series: ACO Colloquium

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.

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.

Series: ACO Colloquium

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.

Series: ACO Colloquium

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.

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.

Series: ACO Colloquium

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.)

Series: ACO Colloquium

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.

Series: ACO Colloquium

(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.