Seminars and Colloquia by Series

Strong bounds for three-term progressions

Series
ACO Colloquium
Time
Friday, June 30, 2023 - 11:00 for 1 hour (actually 50 minutes)
Location
Klaus 2100
Speaker
Raghu Meka – UCLA

Suppose you have a set S of integers from {1,2,...,N} that contains at least N / C elements. Then for large enough N, must S contain three equally spaced numbers (i.e., a 3-term arithmetic progression)?

In 1953, Roth showed this is the case when C is roughly (log log N). Behrend in 1946 showed that C can be at most exp(sqrt(log N)). Since then, the problem has been a cornerstone of the area of additive combinatorics. Following a series of remarkable results, a celebrated paper from 2020 due to Bloom and Sisask improved the lower bound on C to C = (log N)^(1+c) for some constant c > 0.

This talk will describe a new work showing that C can be as big as exp((log N)^0.08), thus getting closer to Behrend's construction. Based on joint work with Zander Kelley

Towards the sunflower conjecture

Series
ACO Colloquium
Time
Monday, November 25, 2019 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Shachar Lovett – University of California, San Diego, CA

A sunflower with $r$ petals is a collection of $r$ sets so that the intersection of each pair is equal to the intersection of all. Erdos and Rado in 1960 proved the sunflower lemma: for any fixed $r$, any family of sets of size $w$, with at least about $w^w$ sets, must contain a sunflower. The famous sunflower conjecture is that the bound on the number of sets can be improved to $c^w$ for some constant $c$. Despite much research, the best bounds until recently were all of the order of $w^{cw}$ for some constant c. In this work, we improve the bounds to about $(\log w)^{w}$.

There are two main ideas that underlie our result. The first is a structure vs pseudo-randomness paradigm, a commonly used paradigm in combinatorics. This allows us to either exploit structure in the given family of sets, or otherwise to assume that it is pseudo-random in a certain way. The second is a duality between families of sets and DNFs (Disjunctive Normal Forms). DNFs are widely studied in theoretical computer science. One of the central results about them is the switching lemma, which shows that DNFs simplify under random restriction. We show that when restricted to pseudo-random DNFs, much milder random restrictions are sufficient to simplify their structure.

Joint work with Ryan Alweiss, Kewen Wu and Jiapeng Zhang.

A proof of the Sensitivity Conjecture

Series
ACO Colloquium
Time
Thursday, September 26, 2019 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Hao Huang – Emory University
In the n-dimensional hypercube graph, one can easily choose half of the vertices such that they induce an empty graph. However, having even just one more vertex would cause the induced subgraph to contain a vertex of degree at least \sqrt{n}. This result is best possible, and improves a logarithmic lower bound shown by Chung, Furedi, Graham and Seymour in 1988. In this talk we will discuss a very short algebraic proof of it.
 

As a direct corollary of this purely combinatorial result, the sensitivity and degree of every boolean function are polynomially related. This solves an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.

Completely log-concave polynomials and matroids

Series
ACO Colloquium
Time
Friday, April 12, 2019 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Cynthia Vinzant – North Carolina State University, Raleigh, NC

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

Complex zeros and algorithms in hard problems of combinatorial counting

Series
ACO Colloquium
Time
Tuesday, February 27, 2018 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Alexander Barvinok – University of Michigan –
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.)

A constant-factor approximation algorithm for the asymmetric traveling salesman problem

Series
ACO Colloquium
Time
Thursday, September 21, 2017 - 13:30 for 1.5 hours (actually 80 minutes)
Location
Skiles 005
Speaker
Laszlo Vegh – London School of Economics –
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.

Symmetry and Turan Sums of Squares

Series
ACO Colloquium
Time
Monday, April 18, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Annie Raymond – University of Washington, Seattle, WA –
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.

Signrank and its applications in combinatorics and complexity

Series
ACO Colloquium
Time
Friday, November 13, 2015 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Noga Alon – Tel Aviv University and IAS, Princeton

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

Towards a structure theory for immersions

Series
ACO Colloquium
Time
Friday, August 21, 2015 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Paul Wollan – University of Rome "La Sapienza"

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

The reduction of PPAD linear complementarity problems to bimatrix games

Series
ACO Colloquium
Time
Thursday, March 27, 2014 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 268
Speaker
Ilan Adler – University of California, Berkeley
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.

Pages