Organizers : Jeff Kahn, Bhargav Narayanan, and Abigail Raz
Date: April 30th, 2018
Speaker: Sebastian Cioaba, U. Delaware
Title: The smallest eigenvalues of some Hamming and Johnson graphs
Abstract: The smallest eigenvalue of a graph is closely related to other graph parameters such as the independence number, the chromatic number or the max-cut. In this talk, I will describe some of the connections between the smallest eigenvalue and the max-cut of a graph that have motivated various researchers such as Karloff, Alon, Sudakov, Van Dam, Sotirov to investigate the smallest eigenvalue of Hamming and Johnson graphs. I will outline our proofs of a 2016 conjecture by Van Dam and Sotirov on the smallest eigenvalue of (distance-j) Hamming graphs and a 1999 conjecture by Karloff on the smallest eigenvalue of (distance-j) Johnson graphs and mention some open problems. This is joint work with Andries Brouwer, Ferdinand Ihringer and Matt McGinnis.
Date: April 23rd, 2018
Speaker: Shay Moran, IAS
Title: On the expressiveness of comparison queries
Abstract: Comparisons are a classical and well studied algorithmic tool that is used in a variety of contexts and applications. We will discuss two manifestations of the expressiveness of these queries in machine learning and complexity theory (a more detailed overview is given below). Both manifestations are based on the notion of "inference dimension” that can be viewed as another instance of the fruitful link between machine learning and discrete mathematics - a link dating back to the discovery of the VC dimension.
1) Active classification with comparison queries [Kane, Lovett, Moran, Zhang ’17]
Active learning is a model for semi-supervised learning that captures situations in which unlabeled data is abundant and manually labelling it is expensive.
We consider an extension of active learning in which the learning algorithm may ask the annotator to compare the distances of two examples from the boundary of their label-class. For example, in a recommendation system application (say for restaurants), the annotator may be asked whether she liked or disliked a specific restaurant (a label query); or which one of two restaurants did she like more (a comparison query). We prove that the usage of comparison queries leads to an exponential improvement in the query complexity of some well studied problems. Specifically, for the class of half-spaces, we show that under natural assumptions, such as large margin or bounded bit-description of the input examples, it is possible to reveal all the labels of a sample of size n using approximately O(logn) queries.
2) Nearly optimal linear decision trees for k-SUM and related problems [Kane, Lovett, Moran ’17]
We use the above framework to construct linear decision trees for a variety of decision problems in combinatorics and discrete geometry. For example, for any constant k, we construct linear decision trees that solve the k-SUM problem on n elements using O(n log n) linear queries. Moreover, the queries we use are comparison queries, which compare the sums of two k-subsets; when viewed as linear queries, comparison queries are 2k-sparse and have only {-1,+1} coefficients.
We give similar constructions for sorting sumsets A+B and for solving the SUBSET-SUM problem, both with optimal number of queries, up to poly-logarithmic terms.
Date: April 16th, 2018
Speaker: Yufei Zhao, MIT
Title: Tower-type bounds for Roth's theorem with popular differences
Abstract: A famous theorem of Roth states that for any $\alpha > 0$ and $n$ sufficiently large in terms of $\alpha$, any subset of $\{1, \dots, n\}$ with density $\alpha$ contains a 3-term arithmetic progression. Green developed an arithmetic regularity lemma and used it to prove that not only is there one arithmetic progression, but in fact there is some integer $d > 0$ for which the density of 3-term arithmetic progressions with common difference $d$ is at least roughly what is expected in a random set with density $\alpha$. That is, for every $\epsilon > 0$, there is some $n(\epsilon)$ such that for all $n > n(\epsilon)$ and any subset $A$ of $\{1, \dots, n\}$ with density $\alpha$, there is some integer $d > 0$ for which the number of 3-term arithmetic progressions in $A$ with common difference $d$ is at least $(\alpha^3-\epsilon)n$. We prove that $n(\epsilon)$ grows as an exponential tower of 2's of height on the order of $\log(1/\epsilon)$. We show that the same is true in any abelian group of odd order $n$. These results are the first applications of regularity lemmas for which the tower-type bounds are shown to be necessary. Joint work with Jacob Fox and Huy Tuan Pham.
Date: April 9th, 2018
Speaker: Thomas Lidbetter, Rutgers
Title: Games of Hide-and-seek with Balls in Boxes
Abstract: We consider zero-sum games in which one player (the Hider) hides k balls among n boxes and the other player (the Searcher) inspects the boxes one by one until finding all k balls. The Searcher has to pay a cost to inspect each box, and may or may not be limited to finding at most one ball each time she inspects a box. We may consider two different objectives for the Searcher: to minimize the total cost incurred in finding all the balls, or to minimize her regret, which is the total cost minus what she'd pay if she knew where all the balls were. We seek optimal (min-max) solutions for both players. No knowledge of game theory will be assumed - the fundamentals of zero-sum games will be explained.
Date: April 2nd, 2018
Speaker: Aditya Potukuchi, Rutgers
Title: On the hardness of coloring rainbow-colorable hypergraphs
Abstract: A (uniform) hypergraph is c-colorable if its vertices can be assigned colors from 1,...,c so that no hyperedge is monochromatic. A hypergraph is r-rainbow colorable (or r-polychromatic) if its vertices can be assigned colors from 1,...,r so that every edge has all r colors. It is very easy to see that if a hypergraph is r-rainbow colorable for r \geq 2, then it is 2-colorable. However, given a hypergraph with the promise that is r-rainbow colorable for r \geq 2, finding an efficient algorithm that outputs a proper 2-coloring of it does not always seem to be an easy problem. This result shows that finding a c-coloring of a k-uniform, k(1 - o_c(1))-rainbow colorable hypergraph is NP-hard. The gadgets involved in the reduction are some kinds of variations/generalizations of the Kneser hypergraph, some of which seem to be well studied, and some which are not (as far as we know). This is based on joint work with Per Austrin and Amey Bhangale.
Date: March 26th, 2018
Speaker: Eyal Lubetzky, NYU
Title: Asymptotics in bond percolation on expanders
Abstract: We consider supercritical bond percolation on a family of high-girth $d$-regular expanders. Alon, Benjamini and Stacey (2004) established that its critical probability for the appearance of a linear-sized (``giant'') component is $p_c=1/(d-1)$. Our main result recovers the sharp asymptotics of the size and degree distribution of the vertices in the giant at any $p>p_c$, as well as that of its 2-core. It was further shown in [ABS04] that the second largest component, at any $0 < p < 1$, has size at most $n^{\omega}$ for some $\omega<1$. We show that, unlike the situation in the classical Erd\H{o}s--R\'enyi random graph, the second largest component in bond percolation on a regular expander, even with an arbitrarily large girth, can have size $n^{\omega'}$ for $\omega'$ arbitrarily close to $1$. Moreover, as a by-product of that construction, we answer negatively a question of Benjamini (2013) on the relation between the diameter of a component in percolation on expanders and the existence of a giant component. Finally, we establish other typical features of the giant component, e.g., the existence of a linear path. Joint work with M. Krivelevich and B. Sudakov.
Date: March 19th, 2018
Speaker: Henry Towsner, Penn
Title: Hypergraphs and higher dimension analogs of VC dimension
Abstract: The notion of bounded VC dimension is a property at the intersection of combinatorics and probability. This family has been discovered repeatedly and studied from various perspectives - for instance, in model theory, theories with bounded VC dimension are known as NIP (the theories which do Not have the Independence Property). One useful property is that graphs with bounded VC dimension are the graphs that can be always be finitely approximated in a "random-free" way: graphs with bounded VC dimension satisfy a strengthening of Szemeredi's Regularity Lemma in which the densities between the pieces of the partition are either close to 0 or close to 1. The generalization of VC dimension to higher arity, known in model theory as k-NIP for various k, has been less well-studied. We summarize some known facts about this generalization, including a new result (joint with Chernikov) showing k-NIP hypergraphs have a similar kind of random-free approximation. To define this notion cleanly, we will need to use a measure-theoretic approach to working with hypergraph regularity.
Date: March 5th, 2018
Speaker: Oanh Nguyen, Princeton
Title: Universality of random functions
Abstract: In this talk, we will discuss recent progress in the study of random functions with a focus on a general framework to prove some universality properties of the roots of random functions. We illustrate how to apply this framework to some popular models of random functions such as random Kac polynomials, random trigonometric polynomials, random Taylor series, and so on. This is joint work with Van Vu.
Date: February 26th, 2018
Speaker: Noga Alon, Princeton and Tel Aviv University
Title: Cayley graphs and list-decodable zero-rate codes
Abstract: What is the maximum possible number of words in a binary code of length n so that there is no Hamming ball of radius (1/4+epsilon)n containing more than two words ? I will show that the answer is Theta(1/epsilon^{3/2}). A crucial ingredient in the proof is a construction of a family of Cayley graphs which is useful in tackling several additional extremal problems in Graph Theory and Geometry. Joint work with Bukh and Polyanskiy.
Date: February 19th, 2018
Speaker: Paul Seymour, Princeton
Title: Gyarfas-Sumner meets Erdos-Hajnal
Abstract: The Gyarfas-Sumner conjecture says that every graph with huge (enough) chromatic number and bounded clique number contains any given forest as an induced subgraph. The Erdos-Hajnal conjecture says that for every graph H, all graphs not containing H as an induced subgraph have a clique or stable set of polynomial size. This talk is about a third problem related to both of these, the following. Say an n-vertex graph is "c-coherent'' if every vertex has degree < cn, and every two disjoint vertex subsets of size at least cn have an edge between them. To prove a given graph H satisfies the Erdos-Hajnal conjecture, it is enough to prove H satisfies the conjecture in all c-coherent graphs and their complements, where c>0 is fixed and as small as we like. But for some graphs H, all c-coherent graphs contain H if c is small enough, so half of the task is done for free. Which graphs H have this property? Paths do (a theorem of Bousquet, Lagoutte, and Thomasse), and non-forests don't. Maybe all forests do? In other words, do all c-coherent graphs with c small enough contain any given forest as an induced subgraph? That question is the topic of the talk. It looks much like the Gyarfas-Sumner conjecture, but it seems easier, and there are already several pretty results. For instance the conjecture is true for all subdivided caterpillars (which is more than we know for Gyarfas-Sumner), and all trees of radius two. Joint work with Maria Chudnovsky, Anita Liebenau, Marcin Pilipczuk, Alex Scott and Sophie Spirkl.
Date: February 12th, 2018
Speaker: Adam Marcus, Princeton
Title: Using rectangular convolutions to construct biregular expanders
Abstract: I will discuss recent advances in the technique we call "the method of interlacing polynomials'' --- a technique that uses polynomials as a way to prove existence theorems in linear algebra. Previous results used this method to show the existence of bipartite Ramanujan graphs of any size and degree, and subsequent progress was made in the work of Cohen in the form of a polynomial time construction. This talk will discuss some recent progress in extending these results to the case of biregular, bipartite expanders. Unlike classical Ramanujan graphs, these new constructions can have partitions of different sizes, making them more suitable for many applications. This is joint work with Aurelien Gribinski.
Date: January 29th, 2018
Speaker: Keith Frankston, Rutgers
Title: On regular 3-wise intersecting families
Abstract: Ellis and Narayanan showed, verifying a conjecture of Frankl, that any 3-wise intersecting family of subsets of {1,2,...,n} admitting a transitive automorphism group has cardinality o(2^n), while a construction of Frankl demonstrates that the same conclusion need not hold under the weaker constraint of being regular. Answering a question of Cameron, Frankl and Kantor from 1989, we show that the restriction of admitting a transitive automorphism group may be relaxed significantly: we prove that any 3-wise intersecting family of subsets of {1,2,...,n} that is regular and increasing has cardinality o(2^n).
Date: January 22nd, 2018
Speaker: Reza Gheissari, NYU
Title: Local MINCUTs and the Ising model on Dense Random Graphs
Abstract: Consider a dense Erdos--Renyi random graph $G(n,p)$ with $p>0$ fixed. Can we partition the graph into two nonempty sets such that every vertex has more neighbors in its own set than in the other? Will a "greedy search" algorithm find such local MINCUTs or will it end up in one of the two trivial partitions $([n],\emptyset)$? We relate these two questions to the local energy minima of an Ising model on the random graph. While we leave open the question of whether/how many nontrivial local minima exist, one might expect that as in similar disordered systems, there are a rapidly diverging (in $n$) number of such local minima. We prove, however, that starting from a typical initial configuration, a dynamic search for local minima avoids all such local minima with high probability and quickly ends up in one of the two homogenous ground states (corresponding to the two trivial partitions).