Video

On the unit distance problem

Abstract: Erdos’ Unit Distances conjecture states that the maximum number of unit distances determined by n points in the plane is almost linear, it is O(n^{1+c}) where c goes to zero as n goes to infinity. In this talk I will survey the relevant results and propose some questions which would imply that the maximum number of unit distances is o(n^{4/3}). 

Video

Abstract: In the talk I will tell about a new deterministic, strongly polynomial time algorithm which can be viewed in two ways. The first is as solving a derandomization problem, providing a deterministic algorithm to a new special case of the PIT (Polynomial Identity Testing) problem. The second is as computing the dimension of the span of a collection of flats in high dimensional space. The talk is based on a joint work with Avi Wigderson.

Video

Ramsey numbers: combinatorial and geometric

Abstract:  In this talk, I will discuss several results on determining the tower growth rate of Ramsey numbers arising in combinatorics and in geometry.  These results are joint work with David Conlon, Jacob Fox, Dhruv Mubayi, Janos Pach, and Benny Sudakov.

Video

Cutting curves into segments and incidence geometry

Video

Polynomials, rank and cap sets

Abstract: In this talk we will look at a new variant of the polynomial method which was first used to prove that sets avoiding 3-term arithmetic progressions in groups like $\mathbb{Z}_4^n$ and $\mathbb{F}_q^n$ are exponentially small (compared to the size of the group). We will discuss lower and upper bounds for the size of the extremal subsets and mention further applications of the method.

The Degeneration Method

Abstract:  In algebraic geometry, a very popular way to study (nice, innocent, nonsingular) varieties is to degenerate them to (weird-looking, badly singular, nonreduced) varieties (which are actually not even varieties but schemes.)  I will talk about some results in combinatorics using this approach (joint with Daniel Erman) and some ideas for future applications of the method.

Video

Abstract: This will be a survey talk about how the polynomial method helps to understand problems in Fourier analysis.  We will review some applications of the polynomial method to problems in combinatorial geometry.  Then we’ll discuss some problems in Fourier analysis, explain the analogy with combinatorial problems, and discuss how to adapt the polynomial method to the Fourier analysis setting.

2:30-3:00pm

The “rank method” in arithmetic complexity: Lower bounds and barriers to lower bounds

Abstract: Why is it so hard to find a hard function? No one has a clue! In despair, we turn to excuses called barriers. A barrier is a collection of lower bound techniques, encompassing as much as possible from those in use, together with a  proof that these techniques cannot prove any lower bound better than the state-of-art (which is often pathetic, and always very far from what we expect for complexity of random functions).

In the setting of  Boolean computation of Boolean functions (where P vs. NP is the central open problem),  there are several famous barriers which provide satisfactory excuses, and point to directions in which techniques may be strengthened.

In the setting of Arithmetic computation of polynomials and tensors (where  VP vs. VNP is the central open problem) we have no satisfactory barriers, despite some recent interesting  attempts.

This talk will describe a new barrier for the Rank Method in arithmetic complexity, which encompass most lower bounds in this field. It also encompass most lower bounds on tensor rank in algebraic geometry (where the the rank method is called Flattening).

I will describe the rank method, explain how it is used to prove lower bounds, and then explain its limits via the new barrier result. As an example, it shows that while the best lower bound on the tensor rank of any explicit 3-dimensional tensor of side n (which is achieved by a rank method) is 2n, no rank method can prove a lower bound which exceeds 8n

(despite the fact that a random such tensor has rank quadratic in n).

No special background knowledge is assumed. The audience is expected to come up with new lower bounds, or else, with new excuses for their absence.

Video

Subspace evasion, list decoding, and dimension expanders

 Abstract: A subspace design is a collection of subspaces of F^n (F = finite field) most of which are disjoint from every low-dimensional subspace of F^n. This notion was put forth in the context of algebraic list decoding where it enabled the construction of optimal redundancy list-decodable codes over small alphabets as well as for error-correction in the rank-metric. Explicit subspace designs with near-optimal parameters have been constructed over large fields based on polynomials with structured roots. (Over small fields, a construction via cyclotomic function fields with slightly worse parameters is known.) Both the analysis of the list decoding algorithm as well as the subspace designs crucially rely on the *polynomial method*.

Subspace designs have since enabled progress on linear-algebraic analogs of Boolean pseudorandom objects where the rank of subspaces plays the role of the size of subsets. In particular, they yield an explicit construction of constant-degree dimension expanders over large fields. While constructions of such dimension expanders are known over any field, they are based on a reduction to a highly non-trivial form of vertex expanders called monotone expanders. In contrast, the subspace design approach is simpler and works entirely within the linear-algebraic realm. Further, in recent (ongoing) work, their combination with rank-metric codes yields dimension expanders with expansion proportional to the degree.

This talk will survey these developments revolving around subspace designs, their motivation, construction, analysis, and connections.

(Based on several joint works whose co-authors include Chaoping Xing, Swastik Kopparty, Michael Forbes, Nicolas Resch, and Chen Yuan.)

Finite reflection groups and graph norms

Abstract: For any given graph $H$, we may define a natural corresponding functional $\|.\|_H$. We then say that $H$ is norming if $\|.\|_H$ is a semi-norm. A similar notion $\|.\|_{r(H)}$ is defined by $\| f \|_{r(H)} := \| | f | \|_H$ and $H$ is said to be weakly norming if $\|.\|_{r(H)}$ is a norm. Classical results show that weakly norming graphs are necessarily bipartite. In the other direction, Hatami showed that even cycles, complete bipartite graphs, and hypercubes are all weakly norming. Using results from the theory of finite reflection groups, we identify a much larger class of weakly norming graphs. This result includes all previous examples of weakly norming graphs and adds many more. We also discuss several applications of our results. In particular, we define and compare a number of generalisations of Gowers’ octahedral norms and we prove some new instances of Sidorenko’s conjecture. Joint work with Joonkyung Lee.

Video

Removal lemmas for triangles and k-cycles.

Abstract: Let p be a fixed prime. A k-cycle in F_p^n is an ordered k-tuple of points that sum to zero; we also call a 3-cycle a triangle. Let N=p^n, (the size of F_p^n). Green proved an arithmetic removal lemma which says that for every k, epsilon>0 and prime p, there is a delta>0 such that if we have a collection of k sets in F_p^n, and the number of k-cycles in their cross product is at most a delta fraction of all possible k-cycles in F_p^n, then we can delete epsilon times N elements from the sets and remove all k-cycles. Green posed the problem of improving the quantitative bounds on the arithmetic triangle removal lemma, and, in particular, asked whether a polynomial bound holds. Despite considerable attention, prior to our work, the best known bound for any k, due to Fox, showed that 1/delta can be taken to be an exponential tower of twos of height logarithmic in 1/epsilon (for a fixed k).

In this talk, we will discuss recent work on Green’s problem. For triangles, we prove an essentially tight bound for Green’s arithmetic triangle removal lemma in F_p^n, using the recent breakthroughs with the polynomial method. For k-cycles, we also prove a polynomial bound, however, the question of the optimal exponent is still open.

The triangle case is joint work with Jacob Fox, and the k-cycle case with Jacob Fox and Lisa Sauermann.

Video

Abstract: Let k>1 be a fixed integer. It is conjectured that any graph on n vertices that can be drawn in the plane without k pairwise crossing edges has O(n) edges. Two edges of a hypergraph cross each other if neither of them contains the other, they have a nonempty intersection, and their union is not the whole vertex set. It is conjectured that any hypergraph on n vertices that contains no k pairwise crossing edges has at most O(n) edges. We discuss the relationship between the above conjectures and explain some partial answers, including a recent result of Kupavskii, Tomon, and the speaker, improving a 40 years old bound of Lomonosov.

Video

Few products, many sums

Abstract: This is what I like calling “weak Erd\H os-Szemer\’edi conjecture”, still wide open over the reals and in positive characteristic. The talk will focus on some recent progress, largely based on the ideas of I. D. Shkredov over the past 5-6 years of how to use linear algebra to get the best out of the Szemer\’edi-Trotter theorem for its sum-product applications. One of the new results is strengthening (modulo the log term hidden in the $\lesssim$ symbol) the textbook Elekes inequality

$$

|A|^{10} \ll |A-A|^4|AA|^4

$$

to

$$|A|^{10}\lesssim |A-A|^3|AA|^5.$$

The other is the bound 

$$E(H) \lesssim |H|^{2+\frac{9}{20}}$$ for additive energy of sufficiently small multiplicative subgroups in $\mathbb F_p$.

Video

Geometric Energies: Between Discrete Geometry and Additive Combinatorics

Abstract: We will discuss the rise of geometric variants of the concept of Additive energy. In recent years such variants are becoming more common in the study of Discrete Geometry problems. We will survey this development and then focus on a recent work with Cosmin Pohoata. This work studies geometric variants of additive higher moment energies, and uses those to derive new bounds for several problems in Discrete Geometry.  

Video

Ranks of matrices with few distinct entries

Abstract: Many applications of linear algebra method to combinatorics rely on the bounds on ranks of matrices with few distinct entries and constant diagonal. In this talk, I will explain some of these application. I will also present a classification of sets L for which no low-rank matrix with entries in L exists.

Video

Submodular minimization and set-systems with restricted intersections

Abstract: Submodular function minimization is a fundamental and efficiently solvable problem class in combinatorial optimization with a multitude of applications in various fields. Surprisingly, there is only very little known about constraint types under which it remains efficiently solvable. The arguably most relevant non-trivial constraint class for which polynomial algorithms are known are parity constraints, i.e., optimizing submodular function only over sets of odd (or even) cardinality. Parity constraints capture classical combinatorial optimization problems like the odd-cut problem, and they are a key tool in a recent technique to efficiently solve integer programs with a constraint matrix whose subdeter-minants are bounded by two in absolute value.

We show that efficient submodular function minimization is possible even for a significantly larger class than parity constraints, i.e., over all sets (of any given lattice) of cardinality r mod m, as long as m is a constant prime power. To obtain our results, we combine tools from Combinatorial Optimization, Combinatorics, and Number Theory. In particular, we establish an interesting connection between the correctness of a natural algorithm, and the non-existence of set systems with specific intersection properties.

Joint work with M. Nagele and R. Zenklusen

Video

Explicit sum-of-squares lower bounds via the polynomial method

Abstract: The sum-of-squares (a.k.a. Positivstellensatz) proof system is a powerful method for refuting systems of multivariate polynomial inequalities, i.e. proving that they have no solutions. These refutations themselves involve sum-of-squares (sos) polynomials, and while any unsatisfiable system of inequalities has a sum-of-squares refutation, the sos polynomials involved might have arbitrarily high degree. However, if a system admits a refutation where all polynomials involved have degree at most d, then the refutation can be found by an algorithm with running time polynomial in N^d, where N is the combined number of variables and inequalities in the system.

Low-degree sum-of-squares refutations appear throughout mathematics. For example, the above proof search algorithm captures as a special case many a priori unrelated algorithms from theoretical computer science; one example is Goemans and Williamson’s algorithm to approximate the maximum cut in a graph. Specialized to extremal graph theory, they become equivalent to flag algebras. They have also seen practical use in robotics and optimal control.

Therefore, it is of interest to identify “hard” systems of low-degree polynomial inequalities that have no solutions but also have no low-degree sum-of-squares refutations. Until recently, the only known examples were either not explicit (i.e., known to exist by non-constructive means such as the probabilistic method) or not robust (i.e., a system is constructed which is not refutable by degree d sos polynomials, but becomes refutable when perturbed by an amount tending to zero with d). We present a new family of instances derived from the cap-set problem, and we show a super-constant lower bound on the degree of its sum-of-squares refutations. Our instances are both explicit and robust.

This is joint work with Sam Hopkins.