This talk will give an overview of  some recent developments and concrete open problems in the GCT program.

This talk will be based on a joint paper with Nicolas Ressayre (https://arxiv.org/pdf/1807.03663.pdf). The paper is devoted to the factorization of multivariate polynomials into products of linear forms, a problem which has applications to differential algebra, to the resolution of systems of polynomial equations and to Waring decomposition (i.e., decomposition in sums of d-th powers of linear forms; this problem is also known as symmetric tensor decomposition). We provide three black box algorithms for this problem. Our main contribution is an algorithm motivated by the application to Waring decomposition. This algorithm reduces the corresponding factorization problem to simultaenous matrix diagonalization, a standard task in linear algebra. The algorithm relies on ideas from invariant theory, and more specifically on Lie algebras. Our second algorithm reconstructs a factorization from several bi-variate projections. Our third algorithm reconstructs it from the determination of the zero set of the input polynomial, which is a union of hyperplanes.

We study the problem of deterministic factorization of sparse polynomials. We show that if f \in \F[x1,…,xn] is a polynomial with s monomials, with individual degrees of its variables bounded by d, then f can be deterministically factored in time s^{O(\poly(d)log n)}.

Prior to our work, the only efficient factoring algorithms known for this class of polynomials were randomized, and other than for the cases of d=1 and d=2, only exponential time deterministic factoring algorithms were known. A crucial ingredient in our proof is a quasi-polynomial sparsity bound for factors of sparse polynomials of bounded individual degree. In particular we show if f is an s-sparse polynomial in n variables, with individual degrees of its variables bounded by d, then the sparsity of each factor of f is bounded by s^{O(d^2 logn)}. This is the first nontrivial bound on factor sparsity for d>2. Our sparsity bound uses techniques from convex geometry, such as the theory of Newton polytopes and an approximate version of the classical Caratheodory's Theorem.

Our work addresses and partially answers a question of von zur Gathen and Kaltofen (JCSS 1985) who asked whether a quasi-polynomial bound holds for the sparsity of factors of sparse polynomials. This is joint work with Shubhangi Saraf and Ilya Volkovich.

Geometric Complexity Theory of Mulmuley and Sohoni aimed to establish lower bounds via the separation of orbit closures of different polynomials: in the case of VP vs VNP this is equivalent to separating the orbit (under general linear group actions) of the permanent from a polynomially sized determinant. The VP vs VNP separation could also be achieved [Nisan] by replacing the determinant polynomial by a matrix power.

The separation of these orbits can be done at the level of their GL-representations and finding occurrence or multiplicity obstructions -- specific irreducible components appearing with distinct multiplicities in the two orbits under consideration. In  [Burgisser-Ikenmeyer-Panova, FOCS'16, JAMS'18] we established that occurrence obstructions (i.e. zero multiplicities for one orbit, but positive for another) for the permanent versus determinant do not occur for determinants of superpolynomial size and hence VP cannot be separated from VNP this way.

In this talk we will discuss how such multiplicities can be studied via classical quantities from combinatorial representation theory (Kronecker and plethysm coefficients) and apply them to establish explicit lower bounds for the non-occurrence of obstructions in the orbits for the permanent versus determinant model ([Ikenmeyer-Panova, FOCS'16, Adv. Math'17]) and also for the orbits of permanent versus matrix power ([Gesmundo-Ikenmeyer-Panova, Diff. Geom. & Its Appl'17]). We will also show how complexity theory can lead to new representation theoretic results and how to approach some other lower bounds problems (like matrix multiplication) with these techniques.

I plan to discuss recent algorithms that beat exhaustive search for solving systems of low-degree polynomial equations over a small finite field, as well as hardness results.
Based on joint work with Brynmor Chapman, Daniel Lokshtanov, Mohan Paturi, Suguru Tamaki, and Huacheng Yu.

A homogeneous depth three circuit C computes a polynomial f = T_1 + T_2 + ... + T_s, where each T_i is a product of d linear forms in n variables. Given black-box access to f, can we efficiently reconstruct (i.e. proper learn) a homogeneous depth three circuit computing f? Learning homogeneous depth three circuits efficiently is stated as an open problem in a work by Klivans and Shpilka (COLT 2003). This is a highly interesting and challenging problem as poly(n,d,s) time learning for homogeneous depth three circuits implies sub-exponential time learning for general arithmetic circuits. We give a randomized poly(n,d,s) time algorithm to reconstruct non-degenerate homogeneous depth three circuits, for n > (3d)^2 and s < (n/3d)^{d/3}. The algorithm works over any field F, provided char(F) = 0 or greater than ds^2, and univariate polynomial factorization over F can be done efficiently. Loosely speaking, a circuit C is non-degenerate if the dimension of the partial derivative space of f equals the sum of the dimensions of the partial derivative spaces of the terms T_1,...,T_s. In this sense, the terms are ``independent'' of each other in a non-degenerate circuit. A random homogeneous depth three circuit (where the coefficients of the linear forms are chosen according to the uniform distribution or any other reasonable distribution) is almost surely non-degenerate. Previous learning algorithms for homogeneous depth three circuits are either improper (with an exponential dependence on d), or they work for constant s (with a doubly exponential dependence on s). Our algorithm hinges on a decomposition of the partial derivative space of f into irreducible invariant subspaces under the action of a shifted differential operator space. The decomposition then leads to the terms of C. To our knowledge, this is the first time the shifted partial derivative operator has been used to make progress on reconstruction algorithms. The technique may also find applications in reconstruction of other circuit classes. Based on joint work with Neeraj Kayal.

Testing whether a set F of polynomials has an algebraic dependence is a basic problem with several applications. The polynomials are given as algebraic circuits. Algebraic independence testing question is wide open over finite fields (Dvir, Gabizon, Wigderson, FOCS'07). In this work we put the problem in AM & coAM. In particular, dependence testing is unlikely to be NP-hard. Our proof method is algebro-geometric-- estimating the size of the image/preimage of the polynomial map F over the finite field. A gap in this size is utilized in the AM protocols. Next, we introduce a new problem called *approximate* polynomials satisfiability (APS). We show that APS is NP-hard and, using projective algebraic-geometry ideas, we put APS in PSPACE (prior best was EXPSPACE via Grobner bases). This has many unexpected applications to approximative complexity theory. This solves an open problem posed in (Mulmuley, FOCS'12, J.AMS 2017); greatly mitigating the GCT Chasm (exponentially in terms of space complexity).

In this talk, we describe two important algorithmic questions in Invariant Theory - the null-cone problem and the orbit closure intersection problem - and show how they arise as special cases of the PIT problem in a very general setting. We then survey special cases of these problems for specific group actions (simultaneous conjugation, left-right action) and state what is known about them, as well as many questions which are still open.

This talk will be inspired by the recently noticed connection [0] between formal (tree) series and non-commutative computations, as a generalization of Nisan's characterization [1] and subsequent results. This provides a clearer understanding of non-commutative computations, possible research directions for general non-commutative circuits and even commutative computations. [0] Nathanaël Fijalkow, Guillaume Lagarde, Pierre Ohlmann: Tight Bounds using Hankel Matrix for Arithmetic Circuits with Unique Parse Trees. Electronic Colloquium on Computational Complexity (ECCC) 25: 38 (2018)

Consider a matrix whose entries are polynomials in indeterminates x1,...,xm. On the one hand, we can substitute random values for the indeterminates x1,...,xm and compute the (generic) rank of the resulting matrix. On the other hand, we can compute its (symbolic) rank as a matrix with entries in the function field. Since rank is captured by vanishing of minors, a simple argument tells us that both computations yield the same answer. Further, elements in the function field can be expanded in terms of power series. The considerations above are crucial steps for the barriers for lower bounds (say for tensor rank) obtainable by reduction to matrix rank in the work of Efremenko, Garg, Oliveira and Wigderson.

In ongoing work with Garg, Oliveira and Wigderson, we are investigating (among other similar things) the possibility of obtaining lower bounds for higher order tensors by reduction to lower order tensors. In proving barriers for these, one needs analogous results for tensors whose entries are polynomials similar to the aforementioned case of matrices. The proof in the matrices case breaks down because tensor rank is not captured by vanishing of polynomials. But the statement remains true, indeed in greater generality. However, its proof now seems to require concepts and results from algebraic geometry, which I will explain in the talk. We hope of the general result will find even more applications in complexity theory.

No special background is assumed."

Let P be a homogeneous polynomial of degree N in m variables. We assume that the polynomial is given as an exact evaluation oracle. Let S be a nontrivial subset of variables, S' is its compliment. Variables are S-separated if P(x1,..,xm) = Q(xi, i \in S) R(xj, j \in S'); monomials are S-splitted if deg(S) + deg(S') = N. In the homogeneous case S-separation implies S-splitting. Our main technical result states that if P is strongly log-concave on an open set then S-splitting implies S-separation. We show that deciding if there exists nontrivial S such that P is S-separable is in BPP, whereas S-splitting is NP-HARD in general. Thus our result gives poly-time randomized algorithm for S-splitting in strongly log-concave case. In the case of H-stable polynomials we present a poly-time deterministic algorithm.