Workshop on Algebraic Complexity Theory

(WACT) 2016

Tel Aviv, Israel

Program


(print version)



February
SunMonTueWedThuFriSat
31 1 2 3 4 5 6
7 8 9 10 11 12 13
Bootcamp
3rd—5th
Workshop
7th—12th
Show all
Select date: February 3   4   5   6   7   8   9   10   11   12  


Location

All the talks (except on Fridays) will happen in Schreiber 006 (in the Schreiber building). Room Schreiber 007 would also be available all day for discussions etc. and so will Schreiber 008 after 1pm.
Sessions on Friday (5th and 12th February) would happen at Beit Hatfutzot, which is right across the Schreiber building.

(Campus map)

References for bootcamp

[SY] Arithmetic circuits: A survey of recent results and open questions (pdf)
by Amir Shpilka and Amir Yehudayoff
[Sapt] A survey of known lower bounds in arithmetic circuits
by Ramprasad Saptharishi

Slides and videos of all speakers may be found below or via the links on navigation bar on top.


February 3rd (Wednesday): Bootcamp Day 1: Basics

Location: Schreiber 006, Tel Aviv University

09:00 — 09:30 Light breakfast
09:30 — 10:20 Amir Shpilka
Introduction I
(video) (agenda)
Basic definitions, VP, VNP, completeness, main problems.
10:20 — 10:40 Coffee break
10:40 — 11:30 Amir Shpilka
Introduction II
(video) (agenda)
Arithmetic circuits, formulas, ABPs, and relations among them. Other complete problems for VP & VNP, Ryser's formula.
References: [Sapt, Chapter 3]
11:30 — 11:40 Short break
11:40 — 12:30 Amir Shpilka
Structural Results I
(video) (agenda)
Interpolation, homogenization, elimination of divisions.
References: [SY, Chapter 2]
12:30 — 14:00 Lunch break (on your own)
14:00 — 14:50 Ramprasad Saptharishi
Structural Results II
(video) (agenda)
Computing partial derivatives, and computing all first-order derivatives simultaneously [Baur-Strassen].
References: [Sapt, Chapter 6.1], [SY, Chapter 2.3]
14:50 — 15:10 Coffee break
15:10 — 16:00 Ramprasad Saptharishi
Depth reduction I
(video) (agenda)
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]
16:00 — 16:10 Short break
16:10 — 17:00 Ankit Gupta
Depth reduction II
(video) (agenda)
Reduction to depth-three [Gupta-Kamath-Kayal-Saptharishi].
References: [Sapt, Chapter 15.2]
(expand all)
(hide all)

February 4th (Thursday): Bootcamp Day 2: Lower bounds and PIT tool-kit

Location: Schreiber 006, Tel Aviv University

09:00 — 09:30 Light breakfast
09:30 — 10:20 Amir Shpilka
Basic Lower Bounds
(video) (agenda)
Counting lower bound, Strassen's lower bound, partial derivative method, lower bounds for depth-3 powering circuits
References: [Sapt, Chapter 6.1, Chapter 7]
10:20 — 10:40 Coffee break
10:40 — 11:30 Ramprasad Saptharishi
Partial Derivative Method I
(video) (agenda)
Lower bounds for hom. depth-3 circuits. Nisan's lower bound for ROABPs.
References: [Sapt, Chapter 7, Chapter 10]
11:30 — 11:40 Short break
11:40 — 12:30 Ramprasad Saptharishi
Partial Derivative Method II
(video) (agenda)
[Raz] lower bound for multilinear formulas and [Raz-Yehudayoff] lower bound for small depth multilinear formuals.
References: [Sapt, Chapter 11], [SY, Chapter 3.6]
12:30 — 14:00 Lunch break (on your own)
14:00 — 14:50 Michael Forbes
Lower Bounds and Polynomial Identity Testing
(video) (agenda)
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]
14:50 — 15:10 Coffee break
15:10 — 16:00 Michael Forbes
Basic PITs
(video) (agenda)
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]
16:00 — 16:10 Short break
16:10 — 17:00 Michael Forbes
Towards PIT for ROABPs
(video) (agenda)
White-box PIT for ROABPs [Raz-Shpilka] and maybe grey-box (known-order) PIT also [Forbes-Shpilka].
References: [SY, Chapter 4.5]
(expand all)
(hide all)

February 5th (Friday): Bootcamp Day 3: Recent Threads

Location: Beit Hatfutzot

09:00 — 09:30 Light breakfast
09:30 — 10:20 Michael Forbes
Translation and Rank-Concentration
(video) (agenda)
Introduction to ideas of shifting and rank concentration of [Agrawal-Saha-Saxena].
10:20 — 10:40 Coffee break
10:40 — 11:30 Chandan Saha
Shifted Partial Derivatives I
(slides) (video) (agenda)
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]
11:30 — 11:40 Short break
11:40 — 12:30 Chandan Saha
Shifted Partial Derivatives II
(video) (agenda)
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]
(expand all)
(hide all)

February 6th (Saturday):

Rest day!



February 7th (Sunday): Workshop Day 1

Location: Schreiber 006, Tel Aviv University

09:00 — 09:30 Light breakfast
09:30 — 10:00 Introductions
10:00 — 10:50 Ketan Mulmuley
Efficient Noether Normalization via GCT I
(video) (abstract)
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.
10:50 — 11:10 Coffee break
11:10 — 12:00 Ketan Mulmuley
Efficient Noether Normalization via GCT II
(video)
12:00 — 12:10 Short break
12:10 — 13:00 Ketan Mulmuley
Efficient Noether Normalization via GCT III
(video)
13:00 — 14:30 Lunch break (on your own)
14:30 — 15:20 Michael Forbes
Some Concrete Questions on the Border Complexity of Polynomials
(video) (abstract)
Algebraic Complexity Theory traditionally studies the size of algebraic circuits required to compute a polynomial p(x1,...,xn). 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(x1,...,xn) 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.
15:20 — 15:40 Coffee break
15:40 — 16:30 Christian Ikenmeyer
Rectangular Kronecker coefficients and plethysms in GCT
(slides) (video) (abstract)
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.
16:30 — Informal talks and discussions

Mrinal Kumar: Lower bounds for locally low algebraic rank circuits

February 8th (Monday): Workshop Day 2

Location: Schreiber 006, Tel Aviv University

09:00 — 09:30 Light breakfast
09:30 — 10:20 Toniann Pitassi
Proof Complexity Tutorial I:
Accomplishments, Connections and Open Problems
(slides) (video)
10:20 — 10:40 Coffee break
10:40 — 11:30 Toniann Pitassi
Proof Complexity Tutorial II
(video)
11:30 — 11:40 Short break
11:40 — 12:30 Pavel HrubeŇ°
Arithmetic circuits and proof complexity I
(slides) (video) (abstract)
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.
12:30 — 14:00 Lunch break (on your own)
14:00 — 14:50 Pavel HrubeŇ°
Arithmetic circuits and proof complexity II
(video)
14:50 — 15:10 Coffee break
15:10 — 16:00 Iddo Tzameret
Characterizing Propositional Proofs as Non-commutative Formulas
(slides) (video) (abstract)
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.
16:00 — 16:10 Short break
16:10 — 17:00 Michael Forbes
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
(video) (abstract)
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={f1,...,fm} of n-variate polynomials have no common solution to the system f1=...=fm=0, then there is a proof of this fact of the following form: there are polynomials G={g1,...,gm} such that f1*g1+...+fm*gm=1 is an identity. From the perspective of computer science, it is most natural to assume that the "boolean axioms" xi2-xi 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 x1+...+xn+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
17:00 —
Informal talks and discussions
 

February 9th (Tuesday): Workshop Day 3

Location: Schreiber 006, Tel Aviv University

09:00 — 09:30 Light breakfast
09:30 — 10:20 Parikshit Gopalan
Pseudorandomness against bounded memory I
The gradually increasing independence paradigm

(slides) (video) (abstract)
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 log2(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.
10:20 — 10:40 Coffee break
10:40 — 11:30 Parikshit Gopalan
Pseudorandomness against bounded memory II
(video)
11:30 — 11:40 Short break
11:40 — 12:30 Parikshit Gopalan
Pseudorandomness against bounded memory III
(video)
12:30 — 14:00 Lunch break (on your own)
14:00 — 14:50 Arpita Korwar
Identity testing for sums of ROABPs
(video) (abstract)
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.
14:50 — 15:10 Coffee break
15:10 — 16:00 Nitin Saxena
Identity testing for constant-width, and commutative, ROABPs
(slides) (video)
16:00 — Informal talks and discussions

Anurag Pandey: Algebraic Independence over positive characteristic

February 10th (Wednesday): Workshop Day 4

Location: Schreiber 006, Tel Aviv University

09:00 — 09:30 Light breakfast
09:30 — 10:20 Rohit Gurjar
Bipartite matching is in quasi-NC
(video) (abstract)
We show that the bipartite perfect matching problem is in quasi-NC2. That is, it has uniform circuits of quasi-polynomial size and O(log2n) 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.
10:20 — 10:40 Coffee break
10:40 — 11:30 Rafael Oliveira
Factors of polynomials of low individual degree
(slides) (video) (abstract)
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.
11:30 — 11:40 Short break
11:40 — 12:30 Open problems session
12:30 — 14:00 Lunch break (on your own)
14:00 — 18:00
Trip to Jaffa
 
18:00 — Open problem session continues over dinner...
at Nanuchka, Tel Aviv.

February 11th (Thursday): Workshop Day 5

Location: Schreiber 006, Tel Aviv University

09:00 — 09:30 Light breakfast
09:30 — 10:20 Ankit Garg
A deterministic polynomial time algorithm for non-commutative rational identity testing
(slides) (video) (abstract)
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.
10:20 — 10:40 Coffee break
10:40 — 11:30 K V Subrahmanyam
Invariants of several matrices under SL(n) x SL(n) action
(slides) (video) (abstract)
Given m, n x n matrices (X1,X2,....,Xm) 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 X1 Bt, AX2Bt,... ,AXmBt). 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 n6 (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 (C1,C2,...,Cm) —, 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.
11:30 — 11:40 Short break
11:40 — 12:30 Mrinal Kumar
Lower bounds for homogeneous depth-5 circuits over small finite fields
(video) (abstract)
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 Fqn to Fq 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.
12:30 — 14:00 Lunch break (on your own)
14:00 — 14:50 Ankit Gupta
Algebraic geometric techniques for depth-4 PIT and Sylvester-Gallai conjectures for varieties
(video) (abstract)
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 F1 + ... + Fk, the algorithm works unless for all i in [k]: V(F1,...,Fi-1,Fi+1,..,Fk) is a subset of V(Fi), where V(F1,..,Fr) denotes the set of common zeroes of F1,..,Fr. 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.
14:50 — 15:10 Coffee break
15:10 — 16:00 Neeraj Kayal
An almost cubic lower bound for depth three arithmetic circuits
(video) (abstract)
There is a family of n-variate multilinear polynomials {fn} in VNP such that any depth three (ΣΠΣ) arithmetic circuit computing fn has size Ω(n3/(log n)2). This improves upon the previously known quadratic lower bound by Shpilka & Wigderson (1999).
16:00 — Informal talks and discussions

Bruno Grenet: Factorization of lacunary polynomials
Gaurav Sinha: Reconstruction of depth-3 circuits of top fan-in 2 over the reals

February 12th (Friday): Workshop Day 6

Location: Beit Hatfutzot, Tel Aviv University

09:00 — 09:30 Light breakfast
09:30 — 10:20 Ben Lee Volk
Identity testing and lower bounds for read-k oblivious ABPs
(slides) (video) (abstract)
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.
10:20 — 10:40 Coffee break
10:40 — 11:30 Amir Yehudayoff
Computing while maintaining symmetries
(slides) (video) (abstract)
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.
11:30 — 11:40 Short break
11:40 — 12:30 Ramprasad Saptharishi
Functional lower bounds for depth-4 circuits and connections to ACC
(video) (abstract)
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}n. 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.
12:30 — 12:40 Conclusion

Important information

  • Boot-camp: 3rd to 5th February, 2016
  • Workshop: 7th to 12th February, 2016
  • Location: Tel Aviv University, Israel


Recent updates




This conference is supported by the European Research Council (ERC),
and also by

Supported by the I-CORE Program of the planning and budgeting committee and The Israel Science Foundation (grant number 4/11),
and also Raymond & Beverly Sackler Faculty of Exact Science.