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 NP-hard problem. We prove that even the question is NP-hard 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.)

Slides

Download video

Peter Bürgisser

The null-cone 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 null-cone 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 null-cone problem has a polynomial time algorithm!

The main evidence for this conjecture is the recent insight that the null-cone 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 null-cone 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 null-cone 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 null-cone 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 null-cone 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 null-cone 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 $\epsilon$-close to a $d$-stochastic 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

Small-depth 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 well-known divide-and-conquer 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 product-depth $\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 product-depth $\Delta$ for the same polynomial of the above form must have a size of $\exp(\Omega(d^{1/\Delta}))$. In particular, any polynomial-sized multilinear formula for $\mathrm{IMM}_d$ must have depth $\Omega(\log d)$, and any polynomial-sized 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.

• Depth-reduction: A well-known 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 depth-reduction in the multilinear setting cannot reduce the depth to $o(\log s)$ without a superpolynomial blow-up 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 non-trivial 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 product-depth $\Delta = o(\log s)$, general formulas of size $s$ and product-depth $\Delta$ cannot be converted to multilinear formulas of size $s^{\omega(1)}$ and product-depth $\Delta$, when the underlying field has characteristic zero.

(Joint work with Nutan Limaye and Srikanth Srinivasan)

Download video

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.

Slides

Download video

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 NP-intermediate status. Another class of problems with NP-intermediate 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 constant-round interactive proof system for the complement of Graph Isomorphism. The approach yields randomized reductions with zero-sided 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/gi-mktp.html)

Slides

Download video

Miklos Santha

On the PPA-completeness of the Combinatorial Nullstellensatz

Friday 11:15 -- 12:00

The Polynomial Parity Argument complexity class PPA consists of NP-search 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 PPA-completeness of two problems whose style is radically different. They are Circuit-CNSS and Circuit-Chevalley, related respectively from the Combinatorial Nullstellensatz and the Chevalley-Warning Theorem over the two elements field. The input of these problems contain PPA-circuits 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 PPA-circuit can be paired in polynomial time.

(Joint work with Alexander Belov, Gábor Ivanyos, Youming Qiao and Siyi Yang.)

Slides

Download video (incomplete)

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 size-$s$ degree-$s$ circuits that depend on the first $\log^{\circ c} s$ variables (where $c$ is a constant and we are composing $c$ logarithms). Thus, hitting-set 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 unheard-of.

Pushing the envelope further we show that:

1. a quadratic-time blackbox PIT for 6913-variate degree-$s$ size-$s$ polynomials, will lead to a "near"-complete derandomization of PIT;

2. a blackbox PIT for $n$-variate degree-$s$ size-$s$ circuits in $s^{n^{\delta}}$ time, for $\delta < 1/2$, will lead to a "near"-complete derandomization of PIT (in contrast, $s^n$-time is trivial);

3. a polynomial-time computable, $O(s^{1.49})$-degree hsg for trivariate depth-$4$ circuits bootstraps to a quasipolynomial time hsg for general poly-degree circuits, and implies a lower bound that is a bit stronger than Kabanets-Impagliazzo (STOC 2003).

(Joint work with Manindra Agrawal & Sumanta Ghosh in STOC'18.) https://www.cse.iitk.ac.in/users/nitin/research.html

Slides

Download video

Yaroslav Shitov

Tensor rank: Counterexamples and applications

Wednesday 11:15 -- 12:15

Tensor rank decompositions have arisen almost a century ago from real-world 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:

1. Strassen’s conjecture on the rank of the direct sum of tensors,
2. Comon’s conjecture on the rank of a symmetric tensor,
3. a complete description of the algorithmic complexity of tensor rank.

Download video

Srikanth Srinivasan

An Exponential Depth-Hierarchy Theorem for Constant-Depth Multilinear Circuits

Tuesday 10:00-11:00

We study the size blow-up that is necessary to convert an algebraic circuit of constant product-depth $D+1$ to one of product-depth $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 product-depth $D+1$ and size $O(n)$, but not by any multilinear circuit of product-depth $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).)

Slides

Download video

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 $k$-SAT instances in different proof-systems. 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.

Slides

Download video

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

Download video