Contributed talks
Prerona Chatterjee
Constructing Faithful Maps over arbitrary fields
Thursday 15:45 -- 16:30
The connection between Algebraic Independence and Polynomial Identity Testing (PIT) was first studied by Beecken-Mittmann-Saxena [BMS'11]. The ideas were then used to solve PITs for non-trivial circuit classes by Agrawal-Saha-Saptharishi-Saxena [ASSS'12]. However, they required the field under consideration to have characteristic zero. The reason was that their technique required constructing "faithful maps", for which they used the Jacobian Criterion, and this required the field to have characteristic zero. Recently however, Pandey-Saxena-Sinhababu [PSS'16] gave a Jacobian-like criterion for fields of arbitrary characteristic. In this talk, we will use the [PSS'16] criterion to construct "faithful maps" for fields of any characteristic. This is a joint work with Ramprasad Saptharishi.
Pranjal Dutta
Discovering the roots: Uniform closure results for algebraic classes under factoring
Wednesday 14:00 -- 15:00
Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. I will talk about generalizing it to a matrix recurrence that approximates all the roots "simultaneously". I will also discuss an interesting property of multivariate polynomial factorization which shows that under a random linear transformation \tau , f(\tau x) completely factors via power series roots. Combining these, I will establish that for an algebraic circuit f(x_1,\dots , x_n) of size s, each factor has size at most a polynomial in: s and the degree of the square-free part of f. For the remaining time, I will talk about different model of interest when the given polynomial f is of degree \mathrm{poly}(n) and can be computed by a formula (resp. Algebraic Branching Program) size n^{O(\log n)}. I will show how to find a similar size formula (resp. ABP) factor in randomized \mathrm{poly}(n^{\log n})-time.
(This is based on joint work with Nitin Saxena (IIT Kanpur) and Amit Sinhababu (IIT Kanpur), STOC'18.)
Rohit Gurjar
Number of near-shortest vectors in lattices and Isolation Lemma
Friday 13:45 -- 14:35
For a matrix A, consider the lattice L(A) formed by all integral vectors v in the null-space of A. We ask for which matrices A, the lattice L(A) has only polynomially many near-shortest vectors i.e., vectors whose length is close to the shortest length in L(A). The motivation for this question comes from the fact that we can derandomize the isolation lemma for any polytope whose faces are described by matrices with the aforementioned property. We show that when the matrix A is totally unimodular (all sub-determinants are 0, +1, or -1) then the lattice L(A) has only polynomially many near-shortest vectors. The proof of this statement goes via a remarkable theorem of Seymour on a decomposition for totally unimodular matrices. The statement generalizes two earlier known results -- the number of near-shortest cycles and the number of near-shorest cuts in a graph are poly-bounded.
(Joint work with Thomas Thierauf and Nisheeth Vishnoi.)
Prahladh Harsha
On Multilinear Forms: Bias, Correlation, and Rank
Thursday 14:30 -- 15:15
This talk is motivated by two fundamental "explicit construction" questions in complexity theory: finding functions uncorrelated with low degree polynomials, and finding tensors with high tensor rank. While trying to answer these questions, we prove a number of new relations and revisit known relations between the bias of multilinear maps, the correlation between multilinear maps and lower degree polynomials, and the tensor rank of tensors.
(Joint work with Abhishek Bhrushundi, Pooya Hatami, Swastik Kopparty and Mrinal Kumar.)
Arpita Korwar
On the limitations of the Shpilka-Volkovich Generator
Wednesday 15:00 -- 15:30
The Shpilka Volkovich (SV) map takes a polynomial over n variables and maps it to a polynomial over k variables, where k << n. It is built using the Lagrange interpolation. Andersen and Volkovich [AV15] show that SV acts as a hitting set for read-once formulas. Forbes, Saptharishi and Shpilka [FSS14] used it for giving hitting sets for commutative ROABPs.
We wish to find a family of polynomials with the 'smallest' parameters that evaluates to 0 when the Shilka-Volkovich map is applied to it. In this talk, we will describe one approach towards this end.
(Joint work with Hervé Fournier.)
François Le Gall
Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor
Thursday 14:00 -- 14:30
In the past few years, successive improvements of the asymptotic complexity of square matrix multiplication have been obtained by developing novel methods to analyze the powers of the "Coppersmith-Winograd tensor", a basic construction introduced thirty years ago. In this talk I will describe how to generalize this approach to make progress on the complexity of rectangular matrix multiplication as well, by developing a framework to analyze powers of tensors in an asymmetric way. By applying this methodology to the fourth power of the Coppersmith-Winograd tensor, I will then show how to improve the complexity of rectangular matrix multiplication.
Pierre Ohlmann
Tight bounds using Hankel Matrix for Arithmetic Circuits with Unique Parse Trees
Monday 14:45 -- 15:15
We establish a fruitful correspondance between Algebraic Branching Programs (ABPs) and weighted automata on words in the first place, and then between Unique Parse Tree (UPT) circuits and weighted automata on trees. We then obtain tight bounds for such circuits, using well known minimisation theorems on wieghted automata. For words and APBs, we obtain Nisan's celebrated result. For trees and UPT circuits, we obtain the first general tight bounds.
(Joint work with Guillaume Lagarde and Nathanaël Fijalkow.)
Anamay Tengse
Hitting Sets for Circuits with Restricted Parse Trees
Tuesday 15:00 -- 15:30
Algebraic branching programs (ABPs) characterize iteratively multiplying matrices that have linear polynomials as their entries. In terms of computational power, ABPs are believed to lie strictly between algebraic formulas and circuits. Although this is not known to be true in the general setting, progress has been made with certain restrictions. In the non-commutative setting, where the variables do not commute, exponential separations are known between ABPs and circuits.
Lagarde, Malod and Perifel [LMP'16] introduced a generalisation of the non-commutative ABPs, called unambiguous circuits. They showed that this model lies strictly between non-commutative ABPs and circuits. Their work along with that of Lagarde, Limaye and Srinivasan [LLS'17] answers the polynomial identity testing (PIT) question for unambiguous circuits in what is called the white-box regime. A white-box PIT algorithm is allowed to access the structure of the circuit and hence is an easier task than the black-box case, where one is allowed only evaluation access.
In this work we study the black-box case, showing that the black-box PIT techniques for non-commutative ABPs due to combined works of Agrawal, Gurjar, Korwar, Saxena and Thierauf [AGKS15][GKST15][GKS16] can be translated to the corresponding settings for unambiguous circuits.
(Joint work with Ramprasad Saptharishi.)