Invited talks
Markus Bläser
Generalized matrix completion problems and algebraic natural proofs
Thursday 11:15  12:15
Algebraic natural proofs were recently introduced by Forbes et al. and independently by Grochow et al. as an attempt to transfer Razborov and Rudichs famous barrier result for Boolean circuit complexity to algebraic complexity theory. Razborov and Rudich's barrier result relies on a widely believed assumption, namely, the existence of pseudorandom generators. Unfortunately, there is no known analogous theory of pseudorandomness in the algebraic setting. Therefore, Forbes et al. use a concept called succinct hitting sets instead. This assumption is related to polynomial identity testing, but it is currently not clear how plausible this assumption is. Forbes et al. are only able to construct succinct hitting sets against rather weak models of arithmetic circuits.
Generalized matrix completion is the following problem: Given a matrix with affine linear forms as entries, find an assignment to the variables in the linear forms such that the rank of the resulting matrix is minimal. We call this rank the completion rank. Computing the completion rank is an NPhard problem. We prove that even the question is NPhard whether a given matrix can be approximated by matrices of completion rank at most b. The minimum quantity b for which this is possible is called border completion rank (similar to the border rank of tensors). Using the hardness result above, we can prove the following barrier: We construct a small family of matrices with affine linear forms as entries and a bound b, such that at least one of these matrices does not have an algebraic natural proof of polynomial size against all matrices of border completion rank b, unless coNP is contained in MA.
With similar techniques, we can also prove that tensor rank is hard to approximate.
(Joint work with Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov.)
Peter Bürgisser
The nullcone problem in invariant theory
Wednesday and Thursday 10:00  11:00
Invariant (and representation) theory studies symmetries by means of group actions. It is a main source of unifying principles in mathematics and physics. Geometric complexity revealed that the fundamental lower bound questions of algebraic complexity are closely related to hard quantitative and computational questions of classical invariant theory.
Suppose a group G acts linearly on a vector space V. The corresponding null cone, which may be thought of the set of "singular objects", consists of those vectors that cannot be distinguished from the zero vector by means of polynomial invariants. The null cone was introduced by Hilbert in his seminal work on invariant theory around 1900. The known algorithms for computing invariants rely on finding a system of polynomial equations for the null cone.
By the nullcone problem we understand the computational problem to decide membership in the null cone. The known algorithms for this problem rely on Gröbner bases and have doubly exponential running time. However, we conjecture that the nullcone problem has a polynomial time algorithm!
The main evidence for this conjecture is the recent insight that the nullcone problem is in NP and coNP, which follows from a duality theory due to Hilbert, Mumford, and Kempf. This is similar as in [BCWW17], where it was shown that membership to moment polytopes is in NP and coNP. Additionally, in the abelian case G=(\mathbb{C}^*)^n, the nullcone problem reduces to the feasibility problem of linear programming.
In the special case of the simultaneous left/right action on tuples of matrices, a polynomial time algorithm for the nullcone problem was recently provided in [GGOW15]. In this work, a deterministic polynomial time algorithm for noncommutative rational identity testing was discovered. Remarkably, despite the algebraic nature of the nullcone problem, the underlying algorithm is numerical: an alternating minimization algorithm, called operator scaling. (For the fascinating connections of this to many areas of CS and math, see Wigderson's tutorial at CCC'17.)
For simultaneous left/right action on tuples of matrices, an explicit system of invariants is known [ANS10] and by recent work of Derksen and Makam [DM17], one can restrict to invariants of small degree. This also led to an algebraic polynomial time algorithm for the nullcone problem [IQS17] in this setting.
If we replace matrices by tensors, we know much less. Specifically, we are interested in V=\mathbb{C}^{n_1}\otimes\cdots\otimes\mathbb{C}^{n_d} with the group G=\mathrm{SL}_{n_1}\times\cdots\times\mathrm{SL}_{n_d} acting by tensor product. This situation arises when studying tensor rank. In the recent paper [BGOWW18] we provided single exponential time algorithms for the nullcone problem. Actually, we found two (deterministic) algorithms: an algebraic one, that works in wide generality (not only for tensors) and relies on Cayley's Omega process and an exponential bound for invariants due to Derksen. The other algorithm works by operator scaling: given a tensor X\in V of bit size at most b, it either identifies that X is in the null cone or outputs a "scaling" Y\in G\cdot X that is \epsilonclose to a dstochastic tensor. The running time is \mathrm{poly}(n_1\cdots n_d,b,\frac{1}{\epsilon}). For obtaining a polynomial time algorithm, it would be enough to replace \frac{1}{\epsilon} by \log\frac{1}{\epsilon}. We hope that such improvement is possible by numerical algorithms with adaptive stepsize. The situation looks promising due to the rich underlying mathematical structure.
(Joint work with A. Garg, R. Oliveira, M. Walter, and A. Wigderson.)
Download video (part 1) Download video (part 2)
Suryajith Chillara
Smalldepth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
Tuesday 11:15  12:00
The complexity of Iterated Matrix Multiplication is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within P. In this paper, we study the algebraic formula complexity of multiplying d many 2 \times 2 matrices, denoted \mathrm{IMM}_d, and show that the wellknown divideandconquer algorithm cannot be significantly improved at any depth, as long as the formulas are multilinear.
Formally, for each depth \Delta \leq \log d, we show that any productdepth \Delta multilinear formula for \mathrm{IMM}_d must have size \exp(\Omega(\Delta d^{1/\Delta})). It also follows from this that any multilinear circuit of productdepth \Delta for the same polynomial of the above form must have a size of \exp(\Omega(d^{1/\Delta})). In particular, any polynomialsized multilinear formula for \mathrm{IMM}_d must have depth \Omega(\log d), and any polynomialsized multilinear circuit for \mathrm{IMM}_d must have depth \Omega(\log d/\log \log d). Both these bounds are tight up to constant factors.
Our lower bound has the following consequences for multilinear formula complexity.

Depthreduction: A wellknown result of Brent (JACM 1974) implies that any formula of size s can be converted to one of size s^{O(1)} and depth O(\log s); further, this reduction continues to hold for multilinear formulas. On the other hand, our lower bound implies that any depthreduction in the multilinear setting cannot reduce the depth to o(\log s) without a superpolynomial blowup in size.

Separations from general formulas: Shpilka and Yehudayoff (FnTTCS 2010) asked whether general formulas can be more efficient than multilinear formulas for computing multilinear polynomials. Our result, along with a nontrivial upper bound for \mathrm{IMM}_d implied by the results of Gupta, Kamath, Kayal and Saptharishi (SICOMP 2016), shows that for any size s and productdepth \Delta = o(\log s), general formulas of size s and productdepth \Delta cannot be converted to multilinear formulas of size s^{\omega(1)} and productdepth \Delta, when the underlying field has characteristic zero.
(Joint work with Nutan Limaye and Srikanth Srinivasan)
Meena Mahajan
(Min,+) formulas, Max, and Shortest Paths
Monday 10:00  10:45
In this talk I will describe a tight bound for computing the maximum of n natural numbers as the difference of two (min,+) formulas. I will also describe some partial results concerning the computation of shortest path lengths via bounded depth (min,+) formulas.
Dieter van Melkebeek
Isomorphism Problems and Minimum Circuit Size
Tuesday 14:00  15:00
The isomorphism problem for a family of group actions asks whether two given elements of the universe belong to the same orbit under the action. Many isomorphism problems have NPintermediate status. Another class of problems with NPintermediate status are certain compressibility questions for Boolean functions, including the Minimum Circuit Size Problem (MCSP): Given a function table and an integer k, does there exist a circuit of size at most k that computes the function?
We present an approach to establish reductions from isomorphism problems to compressibility problems that is inspired by the constantround interactive proof system for the complement of Graph Isomorphism. The approach yields randomized reductions with zerosided error from a broad class of isomorphism problems to the problem of compressibility by short efficient programs (known as MKTP).
(Joint work with Eric Allender, Joshua Grochow, Cris Moore, and Andrew Morgan. Link: http://pages.cs.wisc.edu/~dieter/Research/gimktp.html)
Miklos Santha
On the PPAcompleteness of the Combinatorial Nullstellensatz
Friday 11:15  12:00
The Polynomial Parity Argument complexity class PPA consists of NPsearch problems which are reducible to the parity principle in undirected graphs. It contains a wide variety of interesting problems from graph theory, combinatorics, algebra and number theory. A few complete problems have also been identified in the class, all of which are discretizations or combinatorial analogs of topological fixed point theorems.
Here we prove the PPAcompleteness of two problems whose style is radically different. They are CircuitCNSS and CircuitChevalley, related respectively from the Combinatorial Nullstellensatz and the ChevalleyWarning Theorem over the two elements field. The input of these problems contain PPAcircuits which are arithmetic circuits with special symmetric properties that assure that the polynomials computed by them have always an even number of zeros. In the proof of the result we relate the multilinear degree of the polynomials to the parity of the maximal parse subcircuits that compute monomials with maximal multilinear degree, and we show that the maximal parse subcircuits of a PPAcircuit can be paired in polynomial time.
(Joint work with Alexander Belov, Gábor Ivanyos, Youming Qiao and Siyi Yang.)
Nitin Saxena
Bootstrapping variables in algebraic circuits
Monday 11:00  12:15
We show that for the blackbox polynomial identity testing (PIT) problem it suffices to study circuits that depend only on the first extremely few variables. One only need to consider sizes degrees circuits that depend on the first \log^{\circ c} s variables (where c is a constant and we are composing c logarithms). Thus, hittingset generator (hsg) manifests a bootstrapping behavior a partial hsg against very few variables can be efficiently grown to a complete hsg. A boolean analog, or a pseudorandom generator property of this type, is unheardof.
Pushing the envelope further we show that:

a quadratictime blackbox PIT for 6913variate degrees sizes polynomials, will lead to a "near"complete derandomization of PIT;

a blackbox PIT for nvariate degrees sizes circuits in s^{n^{\delta}} time, for \delta < 1/2, will lead to a "near"complete derandomization of PIT (in contrast, s^ntime is trivial);

a polynomialtime computable, O(s^{1.49})degree hsg for trivariate depth4 circuits bootstraps to a quasipolynomial time hsg for general polydegree circuits, and implies a lower bound that is a bit stronger than KabanetsImpagliazzo (STOC 2003).
(Joint work with Manindra Agrawal & Sumanta Ghosh in STOC'18.) https://www.cse.iitk.ac.in/users/nitin/research.html
Yaroslav Shitov
Tensor rank: Counterexamples and applications
Wednesday 11:15  12:15
Tensor rank decompositions have arisen almost a century ago from realworld applications, and nowadays they became an important tool in pure mathematics as well. A particular challenge important for algebraic complexity theory is to develop strong lower bounding techniques for tensor rank. I will explain how to solve several problems for which the lack of such techniques was a major difficulty:
 Strassen’s conjecture on the rank of the direct sum of tensors,
 Comon’s conjecture on the rank of a symmetric tensor,
 a complete description of the algorithmic complexity of tensor rank.
Srikanth Srinivasan
An Exponential DepthHierarchy Theorem for ConstantDepth Multilinear Circuits
Tuesday 10:0011:00
We study the size blowup that is necessary to convert an algebraic circuit of constant productdepth D+1 to one of productdepth D in the multilinear setting.
We show that for every constant D\geq 1, there is an explicit multilinear polynomial P_D on n variables that can be computed by a multilinear formula of productdepth D+1 and size O(n), but not by any multilinear circuit of productdepth D and size less than \exp(n^{a_D}) where a_D is some constant that depends on D.
This strengthens a result of Raz and Yehudayoff (Computational Complexity 2009) who proved a quasipolynomial separation, and a result of Kayal, Nair and Saha (STACS 2016) who give an exponential separation in the case D=1.
(Joint work with Suryajith Chillara (CSE IITB), Christian Engels (CSE IITB) and Nutan Limaye (CSE IITB).)
Iddo Tzameret
Emerging Connections between Algebraic and Proof Complexity
Friday 10:00  11:00
Proof complexity aims to lower bound the minimal refutation size of certain families of unsatisfiable kSAT instances in different proofsystems. This is similar to the manner in which algebraic complexity aims to lower bound the minimal algebraic circuit size for computing certain families of polynomials, in different algebraic circuit models. In this talk I will survey recently discovered connections between these two questions.
Ben Lee Volk
Unbalancing Sets and Lower Bounds for Multilinear Circuits
Monday 13:45  14:45
We will see a quadratic circuit lower bound for the model of syntactically multilinear arithmetic circuits. Along the way, we'll discuss a solution for a "discrepancy maximization" type problem in extremal set theory, known as Galvin's problem.
(Joint work with Noga Alon and Mrinal Kumar.)