 This event has passed.
Workshop on Algebraic Methods in Combinatorics
November 13, 2017 @ 6:07 pm  November 17, 2017 @ 6:07 pm
The workshop on Algebraic Methods in Combinatorics will take place November 1317, 2017 at the Center of Mathematical Sciences and Applications, located at 20 Garden Street, Cambridge, MA.
The main focus of the workshop is the application of algebraic method to study problems in combinatorics. In recent years there has been a large number of results in which the use of algebraic technique has resulted in significant improvements to long standing open problems. Such problems include the finite field Kakeya problem, the distinct distance problem of Erdos and, more recently, the capset problem. The workshop will include talks on all of the above mentioned problem as well as on recent development in related areas combining combinatorics and algebra.
Participation: The workshop is open to participation by all interested researchers, subject to capacity. Click here to register.
A list of lodging options convenient to the Center can also be found on our recommended lodgings page.
Confirmed participants include:
 Abdul Basit, Rutgers
 Boris Bukh, Carnegie Mellon University
 Pete L. Clark, University of Georgia
 David Conlon, University of Oxford
 Frank de Zeeuw, EPFL
 Thao Thi Thu Do, MIT
 Noam Elkies, Harvard University
 Jordan Ellenberg, University of Wisconsin
 Dion Gijswijt, Delft Institute of Technology
 Sivankanth Gopi, Princeton University
 Venkatesan Guruswami, Carnegie Mellon University
 Marina Iliopoulou, University of California, Berkeley
 Robert Kleinberg, Cornell University
 Michael Krivelevich, Tel Aviv University
 Vsevelod Lev, University of Haifa at Oranim
 László Miklós Lovász, UCLA
 Ben Lund, Rutgers
 Péter Pach, Budapest University of Technology and Economics
 János Pach, New York University
 Zuzana Patáková, Institute of Science and Technology Austria
 Orit Raz, Institute for Advanced Study
 Oliver RocheNewton, Johannes Kepler University
 Misha Rudnev, University of Bristol
 Adam Sheffer, California Institute of Technology
 Amir Shpilka, TelAviv University
 Noam Solomon, Harvard CMSA
 Jozsef Solymosi, University of British Columbia
 Benny Sudakov, ETH, Zurich
 Andrew Suk, University of California, San Diego
 Tibor Szabó, Freie Universität Berlin
 Chris Umans, California Institute of Technology
 Avi Wigderson, Princeton University
 Josh Zahl, University of British Columbia
Coorganizers of this workshop include Zeev Dvir, Larry Guth, and Shubhangi Saraf.
Click here for a list of registrants.
Monday, Nov. 13
Time  Speaker  Title/Abstract 
9:009:30am  Breakfast  
9:3010:30am  Jozsef Solymosi

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}). 
10:3011:00am  Coffee Break  
11:0012:00pm

Orit Raz  Intersection of linear subspaces in R^d and instances of the PIT problem
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. 
12:001:30pm  Lunch  
1:302:30pm  Andrew Hoon Suk 
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. 
2:303:00pm  Coffee Break  
3:004:00pm  Josh Zahl 
Cutting curves into segments and incidence geometry 
4:006:00pm  Welcome Reception 
Tuesday, Nov. 14
Time  Speaker  Title/Abstract 
9:009:30am  Breakfast  
9:3010:30am  Péter Pál Pach 
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 3term 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. 
10:3011:00am  Coffee Break  
11:0012:00pm  Jordan Ellenberg 
The Degeneration Method Abstract: In algebraic geometry, a very popular way to study (nice, innocent, nonsingular) varieties is to degenerate them to (weirdlooking, 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. 
12:001:30pm  Lunch  
1:302:30pm  Larry Guth  The polynomial method in Fourier analysis
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:303:00pm 
Coffee Break  
3:004:00pm  Open Problem 
Wednesday, Nov. 15
Time  Speaker  Title/Abstract 
9:009:30am  Breakfast  
9:3010:30am

Avi Wigderson 
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 stateofart (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 3dimensional 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. 
10:3011:00am  Coffee Break  
11:0012:00pm  Venkat Guruswami 
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 lowdimensional subspace of F^n. This notion was put forth in the context of algebraic list decoding where it enabled the construction of optimal redundancy listdecodable codes over small alphabets as well as for errorcorrection in the rankmetric. Explicit subspace designs with nearoptimal 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 linearalgebraic 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 constantdegree 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 nontrivial form of vertex expanders called monotone expanders. In contrast, the subspace design approach is simpler and works entirely within the linearalgebraic realm. Further, in recent (ongoing) work, their combination with rankmetric 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 coauthors include Chaoping Xing, Swastik Kopparty, Michael Forbes, Nicolas Resch, and Chen Yuan.) 
12:001:30pm  Lunch  
1:302:30pm

David Conlon 
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 seminorm. 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.

2:303:00pm  Coffee Break  
3:004:00pm  Laszlo Miklós Lovasz 
Removal lemmas for triangles and kcycles. Abstract: Let p be a fixed prime. A kcycle in F_p^n is an ordered ktuple of points that sum to zero; we also call a 3cycle 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 kcycles in their cross product is at most a delta fraction of all possible kcycles in F_p^n, then we can delete epsilon times N elements from the sets and remove all kcycles. 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 kcycles, 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 kcycle case with Jacob Fox and Lisa Sauermann. 
Thursday, Nov. 16
Time  Speaker  Title/Abstract 
9:009:30am  Breakfast  
9:3010:30am  Janos Pach  Let’s talk about multiple crossings
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. 
10:3011:00am  Coffee Break  
11:0012:00pm  Misha Rudnev 
Few products, many sums Abstract: This is what I like calling “weak Erd\H osSzemer\’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 56 years of how to use linear algebra to get the best out of the Szemer\’ediTrotter theorem for its sumproduct applications. One of the new results is strengthening (modulo the log term hidden in the $\lesssim$ symbol) the textbook Elekes inequality $$ A^{10} \ll AA^4AA^4 $$ to $$A^{10}\lesssim AA^3AA^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$. 
12:001:30pm  Lunch  
1:302:30pm  Adam Sheffer 
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. 
2:303:00pm  Coffee Break  
3:004:00pm  Boris Bukh 
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 lowrank matrix with entries in L exists. 
Friday, Nov. 17
Time  Speaker  Title/Abstract 
9:009:30am  Breakfast  
9:3010:30am  Benny Sudakov 
Submodular minimization and setsystems 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 nontrivial 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 oddcut problem, and they are a key tool in a recent technique to efficiently solve integer programs with a constraint matrix whose subdeterminants 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 nonexistence of set systems with specific intersection properties. Joint work with M. Nagele and R. Zenklusen 
10:3011:00am  Coffee Break  
11:0012:00pm  Robert Kleinberg 
Explicit sumofsquares lower bounds via the polynomial method Abstract: The sumofsquares (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 sumofsquares (sos) polynomials, and while any unsatisfiable system of inequalities has a sumofsquares 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. Lowdegree sumofsquares 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 lowdegree polynomial inequalities that have no solutions but also have no lowdegree sumofsquares refutations. Until recently, the only known examples were either not explicit (i.e., known to exist by nonconstructive 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 capset problem, and we show a superconstant lower bound on the degree of its sumofsquares refutations. Our instances are both explicit and robust. This is joint work with Sam Hopkins. 
12:001:30pm  Lunch 