Program


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 firstorder derivatives simultaneously [BaurStrassen].
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 [ValiantSkyumBerkowitzRackoff] and proof of [AgrawalVinay, 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 depththree [GuptaKamathKayalSaptharishi].
References: [Sapt, Chapter 15.2] 
(expand all) (hide all) 
February 4th (Thursday): Bootcamp Day 2: Lower bounds and PIT toolkit
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 depth3 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. depth3 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 [RazYehudayoff] 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, whitebox, blackbox, generators, SchwartzZippelDeMilloLipton, 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 depth2 circuits [KlivansSpielman], PITs for depth3 powering circuits (using [ShpilkaVolkovich]generator), PIT for readonce 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)
Whitebox PIT for ROABPs [RazShpilka] and maybe greybox (knownorder) PIT also [ForbesShpilka].
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 RankConcentration (video) (agenda)
Introduction to ideas of shifting and rank concentration of [AgrawalSahaSaxena].

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 fanin hom. depth4 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. depth4 and low bottom fanin depth3, variant of skewedshifted 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(x_{1},...,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_{1},...,x_{n}) in some sense. While most existing methods for proving circuit size lower bounds readily extend to proving lower bounds for bordersize, we lack a robust understanding of how the notions of circuitsize and bordercircuitsize compare.
In this talk I will discuss some concrete challenges surrounding bordercomplexity. I will start with the basic setup of border tensorrank, 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 "circuitsize and bordercircuitsize " 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 Noncommutative Formulas (slides) (video) (abstract)
Does every Boolean tautology have a short propositionalcalculus 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 propositionalcalculus 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 propositionalcalculus proofs follow from certain size lower bounds on a fairly weak model of computation, namely, noncommutative 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 noncommutative 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 wellknown proof system is Hilbert's Nullstellensatz, which shows that if the family F={f_{1},...,f_{m}} of nvariate polynomials have no common solution to the system f_{1}=...=f_{m}=0, then there is a proof of this fact of the following form: there are polynomials G={g_{1},...,g_{m}} such that f_{1}*g_{1}+...+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}^{2}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 superpolynomial 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 wellknown 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 /subsetsum axiom/, that x_{1}+...+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 polynomialsize readonce oblivious algebraic branching program (roABP) or depth3 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 subsetsum axiom require superpolynomially large proofs to prove their unsatisfiability when the size of the algebraic circuits are measured as roABPs, sums of powers of lowdegree 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 log^{2}(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, readonce DNFs, and to optimal constructions of hash functions families for loadbalancing, minwise 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 Readonce 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 whitebox identity test for the sum of two ROABPs. We will also study a blackbox 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 constantwidth, 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 quasiNC (video) (abstract)
We show that the bipartite perfect matching problem is in quasiNC^{2}. That is, it has uniform circuits of quasipolynomial size and O(log^{2}n) depth. Previously, only an exponential upper bound was known on the size of such circuits with polylogarithmic 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 noncommutative rational identity testing (slides) (video) (abstract)
We study the noncommutative rational identity testing problem or the word problem for the free skew field of noncommutative 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 noncommutative algebra, it also has various connections to computational complexity and derandomization, 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 (X_{1},X_{2},....,X_{m}) with entries in a field F, the group SL(n,F) x SL(n,F) acts on this mtuple with (A,B) sending the m tuple to (A X_{1} B^{t}, AX_{2}B^{t},... ,AX_{m}B^{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 blowups, Derksen and Vishwambara showed that the invariant ring is generated in degree n^{6} (over infinite fields). I will describe our result, regularity under blowups, 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_{1},C_{2},...,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. 
11:30 — 11:40  Short break 
11:40 — 12:30 
Mrinal Kumar Lower bounds for homogeneous depth5 circuits over small finite fields (video) (abstract)
The last few years have seen substantial progress on the question of proving lower bounds for homogeneous depth4 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 depth5 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 depth4 circuits [Gupta et. al. 13, Fournier et. al. 13, Kayal et. al. 14, KumarSaraf 14] and for nonhomogeneous depth3 circuits over finite fields [GrigorievKarpinski 98, GrigorievRazborov 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}^{n} 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. 
12:30 — 14:00  Lunch break (on your own) 
14:00 — 14:50 
Ankit Gupta Algebraic geometric techniques for depth4 PIT and SylvesterGallai conjectures for varieties (video) (abstract)
We consider the problem of devising polytime blackbox PIT for depth4 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_{1} + ... + F_{k}, the algorithm works unless for all i in [k]: V(F_{1},...,F_{i1},F_{i+1},..,F_{k}) is a subset of V(F_{i}), where V(F_{1},..,F_{r}) denotes the set of common zeroes of F_{1},..,F_{r}. The algorithm goes via solving the radicalideal 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 [BeeckenMittmannSaxena] if certain higherdegree generalizations of the SylvesterGallai 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 nvariate multilinear polynomials {f^{n}} in VNP such that any depth three (ΣΠΣ) arithmetic circuit computing f_{n} has size Ω(n^{3}/(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 
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 readk oblivious ABPs (slides) (video) (abstract)
Readk oblivious algebraic branching programs are a natural generalization of the well studied model of readonce 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 depth4 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 hypercube, 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
 Bootcamp: 3^{rd} to 5^{th} February, 2016
 Workshop: 7^{th} to 12^{th} February, 2016
 Location: Tel Aviv University, Israel
Recent updates
 [20160320] Videos of all lectures added.
 [20160213] Embedded slides of speakers added.
 [20160212] Slides of all speakers added to the program.
 [20160208] Added a pdf with some accessible concrete open problems that were suggested in the workshop.