Basic definitions, VP, VNP, completeness, main problems.

Arithmetic circuits, formulas, ABPs, and relations among them. Other complete problems for VP & VNP, Ryser's formula.
References: [Sapt, Chapter 3]

Interpolation, homogenization, elimination of divisions.
References: [SY, Chapter 2]

Computing partial derivatives, and computing all first-order derivatives simultaneously [Baur-Strassen].
References: [Sapt, Chapter 6.1], [SY, Chapter 2.3]

Depth reduction for formulas, and ABPs. Statement of [Valiant-Skyum-Berkowitz-Rackoff] and proof of [Agrawal-Vinay, Koiran, Tavenas] assuming [VSBR].
References: [Sapt, Chapter 5.2]

Reduction to depth-three [Gupta-Kamath-Kayal-Saptharishi].
References: [Sapt, Chapter 15.2]

Counting lower bound, Strassen's lower bound, partial derivative method, lower bounds for depth-3 powering circuits
References: [Sapt, Chapter 6.1, Chapter 7]

Lower bounds for hom. depth-3 circuits. Nisan's lower bound for ROABPs.
References: [Sapt, Chapter 7, Chapter 10]

[Raz] lower bound for multilinear formulas and [Raz-Yehudayoff] lower bound for small depth multilinear formuals.
References: [Sapt, Chapter 11], [SY, Chapter 3.6]

Definition of PIT, white-box, black-box, generators, Schwartz-Zippel-DeMillo-Lipton, sketch of hardness vs. randomness tradeoff.
References: [SY, Chapter 4.1, 4.2, 4.3]

PIT for depth-2 circuits [Klivans-Spielman], PITs for depth-3 powering circuits (using [Shpilka-Volkovich]-generator), PIT for read-once formulas.
References: [SY, Chapter 4.4, 4.8]

White-box PIT for ROABPs [Raz-Shpilka] and maybe grey-box (known-order) PIT also [Forbes-Shpilka].
References: [SY, Chapter 4.5]

Introduction to ideas of shifting and rank concentration of [Agrawal-Saha-Saxena].

Definition and geometric intuition, lower bounds for low bottom fan-in hom. depth-4 circuits, limitations of the measure and definition of projected shifted partials.
References: [Sapt, Chapter 12]

Applicability of projected shifted partials for hom. depth-4 and low bottom fan-in depth-3, variant of skewed-shifted partials and applications.
References: [Sapt, Chapter 13, 15]

This tutorial will give an overview of the GCT approach to efficient Noether Normalization of the rings of invariants and explicit varieties, and its concrete applications.

Algebraic Complexity Theory traditionally studies the size of algebraic circuits required to compute a polynomial p(x₁,...,x_n). However, from the perspective of algebraic geometry it is more natural to consider the "border size" required to compute a polynomial, which is smallest size of circuits needed to arbitrarily approximate p(x₁,...,x_n) in some sense. While most existing methods for proving circuit size lower bounds readily extend to proving lower bounds for border-size, we lack a robust understanding of how the notions of circuit-size and border-circuit-size compare.

In this talk I will discuss some concrete challenges surrounding border-complexity. I will start with the basic setup of border tensor-rank, and comment on its relation to the matrix multiplication exponent. I will then discuss the natural extension to VP and its border. I will then highlight open questions on the "circuit-size and border-circuit-size " question, even for restricted models of computation, as well as discussing recent challenges posed by Mulmuley.

We disprove an important conjecture in GCT: we prove that the vanishing of rectangular Kronecker coefficients cannot be used to find superpolynomial determinantal complexity lower bounds for the permanent polynomial. We discuss the consequences for the GCT approach. The talk will be accessible for a broad algebraic complexity theory audience.
This is joint work with Greta Panova.

We will discuss topics connecting the fields of proof complexity and arithmetic circuit complexity. One such question is whether Polynomial Identity Testing is in NP, and whether this can be witnessed by a proof system which syntactically manipulates arithmetic circuits. Other topics arise when viewing Boolean proof complexity from arithmetic perspective. This leads to Nullstellensatz based proof systems, such as the Polynomial Calculus, and to questions about the complexity of Nullstellensatz itself.

Does every Boolean tautology have a short propositional-calculus proof? Here, a propositional calculus proof is a proof starting from a set of axioms and deriving new Boolean formulas using a fixed set of sound derivation rules. Establishing any strong size lower bound on propositional-calculus proofs is a major open problem in proof complexity, and among a handful of fundamental hardness questions in complexity theory by and large.

In this talk I will show that lower bounds on propositional-calculus proofs follow from certain size lower bounds on a fairly weak model of computation, namely, non-commutative arithmetic formulas. For this weak model of computation, many strong size lower bounds are already known since the early 90s. The argument is a new characterization of propositional proofs as non-commutative formulas.

Based on a joint work with Fu Li and Zhengyu Wang.

Proof complexity studies the complexity of mathematical proofs, with the aim of exhibiting (true) statements whose proofs are always necessarily long. One well-known proof system is Hilbert's Nullstellensatz, which shows that if the family F={f₁,...,f_m} of n-variate polynomials have no common solution to the system f₁=...=f_m=0, then there is a proof of this fact of the following form: there are polynomials G={g₁,...,g_m} such that f₁*g₁+...+f_m*g_m=1 is an identity. From the perspective of computer science, it is most natural to assume that the "boolean axioms" x_i²-x_i are among the polynomials F, and to ask how succinctly one can express the proof G. Assuming NP!=coNP, there must be systems F such that any proof G requires super-polynomial size to write down, and the goal is to furnish such systems F unconditionally.

Substantial work on the Nullstellensatz system has measured the complexity of G in terms of their degree or sparsity, and obtained the desired lower bounds for these measures. Grochow and Pitassi have recently argued that it is natural to measure the complexity of G by the size needed to express them as algebraic circuits, as this can be exponentially more succinct than counting monomials. They called the resulting system the Ideal Proof System (IPS), and showed that it captures the power of well-known strong proof systems such as the Frege proof system, as well as showing that certain natural lower bounds for the size of IPS proofs would imply VP!=VNP, an algebraic analogue of P!=NP. This is in contrast to other proof systems, where direct ties to computational lower bounds are often lacking.

Motivated by their work, we study the IPS proof system further. We first show that weak subsystems of IPS can be quite powerful. We consider the /subset-sum axiom/, that x₁+...+x_n+1 is unsatisfiable over the boolean cube. In prior work, Impagliazzo, Pudlak, and Sgall showed that any proof of unsatisfiability requires exponentially many monomials to write down. Here, we give an efficient proof even in restricted subclasses of the IPS proof system, showing that the proof can be expressed as a polynomial-size read-once oblivious algebraic branching program (roABP) or depth-3 multilinear formula.

We then consider lower bounds for subclasses of IPS. We obtain certain extensions to existing lower bound techniques, obtaining "functional lower bounds" as well as "lower bounds for multiples". Using these extensions, we show that variants of the subset-sum axiom require super-polynomially large proofs to prove their unsatisfiability when the size of the algebraic circuits are measured as roABPs, sums of powers of low-degree polynomials, or multilinear formulas.

Joint work with Amir Shpilka, Iddo Tzameret, and Avi Wigderson

Pseudorandom number generators (PRGs) which fool certain statistical tests unconditionally are well studied in complexity theory, and have found many applications in algorithm design. In this tutorial, we study PRG constructions for a families of tests that (mostly) use limited memory. A classic result of Nisan shows that log²(n) bits of randomness suffice to fool any algorithm that uses log(n) bits of memory. Improving this to log(n) (proving RL =L) is a long standing challenge in complexity theory.

We will mostly focus on the "gradually increasing independence" paradigm for constructing PRGs, which has recently led to optimal PRGs for several classes of tests including halfspaces, combinatorial rectangles/shapes, read-once DNFs, and to optimal constructions of hash functions families for load-balancing, min-wise hashing and dimension reduction. The PRGs/hash functions given by this paradigm are typically quite simple: they are variants on the XOR/interleaving of a few strings with limited independence. We speculate about other problems in complexity where this paradigm might be interesting.

An Arithmetic Branching Program (ABP) is known to be equivalent to iterated matrix multiplication and determinant computation. i.e. any polynomial computed by an ABP can also be written as a small iterated product of matrices.

The Read-once Oblivious Arithmetic Branching Program (ROABP) is an ABP where a variable is allowed to occur in only one of the matrices of the ABP. We are interested in the complexity of Polynomial Identity Testing (PIT) for this model.

In this talk, we will study a few structural results about ROABP. In the process, we will give a white-box identity test for the sum of two ROABPs. We will also study a black-box test for the sum of two ROABPs. We will then outline how this method can be extended to a sum of constantly many ROABPs.

We show that the bipartite perfect matching problem is in quasi-NC². That is, it has uniform circuits of quasi-polynomial size and O(log²n) depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. We obtain our result by an almost complete derandomization of the famous Isolation Lemma when applied to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem.

Kaltofen [Kal89] proved the remarkable fact that multivariate polynomial factorization can be done efficiently, in randomized polynomial time. Still, more than twenty years after Kaltofen's work, many questions remain unanswered regarding the complexity aspects of polynomial factorization, such as the question of whether factors of polynomials efficiently computed by arithmetic formulas also have small arithmetic formulas, asked by Kopparty, Saraf and Shpilka [KSS14], and the question of bounding the depth of the circuits computing the factors of a polynomial. We are able to answer these questions in the affirmative for the interesting class of polynomials of bounded individual degrees, which contains polynomials such as the determinant and the permanent. This partially answers the question above posed in [KSS14], who asked if this result holds without the dependence on the individual degree. Along the way, we introduce several new technical ideas that could be of independent interest when studying arithmetic circuits (or formulas). In this talk, we will give a brief survey of polynomial factorization and its relations to arithmetic complexity, and give an overview of the ideas used in the proof of our main result.

We study the non-commutative rational identity testing problem or the word problem for the free skew field of non-commutative rational functions. We prove that an existing algorithm due to Gurvits is actually a deterministic polynomial time algorithm for this problem (over the field of rationals). Our analysis is simple, providing explicit bounds on the ``capacity'' measure of completely positive operators, introduced by Gurvits.

This problem has a rich history and has appeared in various forms in a remarkable number of mathematical and computational areas. Besides non-commutative algebra, it also has various connections to computational complexity and de-randomization, commutative invariant theory, quantum information theory and system theory. No special background will be assumed for this talk, as it can be, the problem, algorithm and analysis can be framed in the language of linear algebra. This is joint work with Leonid Gurvits, Rafael Oliveira and Avi Wigderson.

Given m, n x n matrices (X₁,X₂,....,X_m) with entries in a field F, the group SL(n,F) x SL(n,F) acts on this m-tuple with (A,B) sending the m tuple to (A X₁ B^t, AX₂B^t,... ,AX_mB^t). A description of the polynomial functions which are invariant under this action is well known (over infinite fields). This ring of invariant functions is known to be finitely generated. However degree bounds are poor.

Recently, based on our result on the rank of matrix families under blow-ups, Derksen and Vishwambara showed that the invariant ring is generated in degree n⁶ (over infinite fields).

I will describe our result, regularity under blow-ups, and the Derksen and Vishwambara result. I will also indicate how a simple calculation starting with our result yields (almost) the same bounds, without using the Derksen Vishwambara machinery.

I will also show that testing membership in the null cone — do all invariant functions vanish on a given tuple of matrices (C₁,C₂,...,C_m) —, is in polynomial time, improving on a result of Ankit Garg, et al. This also settles the problem of computing in polynomial time the non commutative rank of a family of matrices.

This is joint work with Gabor Ivanyos and Jimmy Qiao.

The last few years have seen substantial progress on the question of proving lower bounds for homogeneous depth-4 circuits which seem to come very close to the VP vs VNP question. Therefore, it is natural to ask whether the techniques developed in this course can be used to show lower bounds for more general classes of arithmetic circuits.

In this talk, we will see a proof of exponential lower bounds for the class of homogeneous depth depth-5 circuits over small finite fields which is a modest step in this direction.

Our proof builds up on the ideas developed on the way to proving lower bounds for homogeneous depth-4 circuits [Gupta et. al. 13, Fournier et. al. 13, Kayal et. al. 14, Kumar-Saraf 14] and for non-homogeneous depth-3 circuits over finite fields [Grigoriev-Karpinski 98, Grigoriev-Razborov 00].

A key insight is to look at the space of shifted partial derivatives of a polynomial as a space of functions from F_qⁿ to F_q as opposed to looking at them as a space of formal polynomials and builds over a tighter analysis of the lowerbound of Kumar and Saraf.

Based on joint work with Ramprasad Saptharishi.

We consider the problem of devising poly-time blackbox PIT for depth-4 circuits with O(1) top and bottom fanins. We devise an algorithm that works unless the intermediate polynomials satisfy a certain degeneracy condition. Informally, for the circuit F₁ + ... + F_k, the algorithm works unless for all i in [k]: V(F₁,...,F_i-1,F_i+1,..,F_k) is a subset of V(F_i), where V(F₁,..,F_r) denotes the set of common zeroes of F₁,..,F_r. The algorithm goes via solving the radical-ideal membership question for the case when the involved polynomials have constant degree factors. We note that the degenerate case can be solved via an algorithm of [Beecken-Mittmann-Saxena] if certain higher-degree generalizations of the Sylvester-Gallai theorem hold.

There is a family of n-variate multilinear polynomials {fⁿ} in VNP such that any depth three (ΣΠΣ) arithmetic circuit computing f_n has size Ω(n³/(log n)²). This improves upon the previously known quadratic lower bound by Shpilka & Wigderson (1999).

Read-k oblivious algebraic branching programs are a natural generalization of the well- studied model of read-once oblivious algebraic branching program (ROABPs). In this talk we will see an exponential lower bound and a subexponential PIT algorithm for this model.

Based on a joint work with Matt Anderson, Michael Forbes, Amir Shpilka and Ramprasad Saptharishi.

Valiant showed that every polynomial f can be represented as the determinant of a matrix M = M(f). The minimum size of such a matrix, denoted dc(f), is a natural complexity measure for f (and is related to its formula size). Landsberg and Ressayre recently defined the notion of equivariant representation. Roughly, this means that the matrix M also respects the symmetries of f. In the talk, we shall discuss this notion and consider some examples.

Recent years have seen a surge of activity in the field of arithmetic circuit lower bounds. Although there has been a tremendous improvement in our understanding of arithmetic circuits, they do not translate to analogues in the boolean world. In this talk, In this talk, we shall look at a possible approach towards strengthening arithmetic circuit lower bounds so that they may have relevance in the boolean world, namely via `functional' lower bounds.

We say that an arithmetic circuit C (over a field F) computes a polynomial P functionally if C(x) = P(x) on all of {0,1}ⁿ. Importantly, C need not compute the same polynomial as P but as long as they agree on the boolean hyper-cube, we shall say C functionally computes P.

In this talk we shall present a way to translate almost all recent lower bounds for shallow arithmetic circuits in to functional lower bounds with some restrictions. Although this does not yet give improve our understanding in the boolean world, it does take a step towards that goal.

This is part of a joint ongoing work with Michael Forbes and Mrinal Kumar.