| Monday, Feb 27, 2017 | ||
|---|---|---|
| 12:30 - 13:45 | Registration, Lunch | |
| 13:50 - 14:00 | Opening remarks | |
| 14:00 - 15:00 | Nutan Limaye | Sum of powers of linear forms. |
| 15:00 - 15:30 | Coffee Break | |
| 15:30 - 16:30 | Nitin Saxena | Algebraic vs Functional independence over any characteristic. |
| 16:30 - 17:00 | Coffee | |
| Tuesday, Feb 28, 2017 | ||
|---|---|---|
| 10:00 - 11:00 | Ramprasad Saptharishi | Separating homogeneous depth-4 and depth-5 arithmetic circuits. |
| 11:00 - 11:45 | Coffee Break | |
| 11:45 - 12:30 | Sumanta Ghosh | On small hitting-sets for tiny arithmetic circuits. |
| 12:30 - 14:00 | Lunch | |
| 14:00 - 15:00 | Ben Lee Volk | Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds. |
| 15:00 - 15:30 | Coffee Break | |
| 15:30 - 16:30 | Discussion | |
| 16:30 - 17:00 | Coffee | |
| Wednesday, Mar 1, 2017 | ||
|---|---|---|
| 10:00 - 11:00 | Partha Mukhopadhyay | Randomized Polynomial Time Identity Testing for Noncommutative Circuits. |
| 11:00 - 11:45 | Coffee Break | |
| 11:45 - 12:30 | Guillaume Malod | Non-commutative computations: lower bounds and polynomial identity testing. |
| 12:30 - 14:00 | Lunch | |
| 14:00 - 15:00 | B V Raghavendra Rao | An exponential lower Bound against depth five powering circuits. |
| 15:00 - 15:30 | Coffee Break | |
| 15:30 - 16:30 | Srikanth Srinivasan | Separation of AC^0[\oplus] Formulas and Circuits. |
| 16:30 - 17:00 | Coffee | |
| 19:00 - 21:00 | Workshop Dinner (at IMSc) | |
| Thursday, Mar 2, 2017 | ||
|---|---|---|
| 10:00 - 11:00 | K V Subrahmanyam | Invariants, Compression spaces, Brascamp-Lieb inequalities. |
| 11:00 - 11:45 | Coffee Break | |
| 11:45 - 12:30 | Gorav Jindal | A deterministic PTAS for commutative rank of matrix spaces. |
| 12:30 - 14:00 | Lunch | |
| 14:00 - 15:00 | Markus Blaeser | Tensors of minimal border rank. |
| 15:00 - 15:30 | Coffee Break | |
| 15:30 - 16:30 | Discussion | |
| 16:30 - 17:00 | Coffee | |
| Friday, Mar 3, 2017 | ||
|---|---|---|
| 10:00 - 11:00 | Vineet Nair | Reconstruction of matrix products |
| 11:00 - 11:45 | Coffee Break | |
| 11:45 - 12:30 | V Arvind | Noncommutative polynomial factorization |
| 12:30 - 12:40 | Closing Remarks | |
| 12:40 - 14:00 | Lunch | |
In this talk we discuss the problem of factorization for polynomials in the free non-commutative ring in $n$ non-commuting variables over a field F. Although it is not a unique factorization ring, it turns out that variable disjoint factorization has the uniqueness property and computing the variable-disjoint factorization is equivalent to non-commutative polynomial identity testing. Variable-disjoint factorization in the black-box setting can be efficiently computed, where the factors computed will be given by black-boxes.
(This is joint work with Pushkar Joglekar and Gaurav Rattan)
All known asymptotically fast matrix multiplication algorithms start with some tensor of very low complexity. Therefore, one potential way to find better algorithms for fast matrix multiplication is to find new starting tensors of very low complexity. In this talk, we present some of the recent progress on understanding the structure of tensors of minimal border rank.
Recent works have shown that to solve identity testing for VP circuits it suffices to focus on the question of designing hitting-sets for constant-depth circuits. In this work we are interested in identifying the smallest model, within depth-4 circuits, whose study would imply results for VP. We show that if we can design poly(s)-time hitting-set for Σ∧^{a}ΣΠ^{O(log s)} circuits of size s, where a = ω(1) and number of variables n = O(log s), then we can solve identity testing for VP in quasipoly-time. We call the former model– tiny diagonal depth-4. Alternatively, we claim that, to understand VP one only needs to find hitting-sets, for depth-4, that have a small parameterized complexity.
One expects that with this severe restriction on a and n, it should be “exponentially” easier to design hitting-sets. Indeed, we give several examples of (log s)-variate circuits where a new measure (called cone-size) helps in devising poly-time hitting-sets, but the same question for their s-variate versions is open till date. For instance, diagonal depth-3 circuits, and in general, models with low partial derivative space.
We also introduce a new concept, called cone-closed basis isolation, and provide example models where it occurs, or can be achieved by a small shift. This refines the previously studied notions of low-support rank concentration and least basis isolation in certain ABP models.
(based on joint work with Manindra Agrawal, Michael Forbes and Nitin Saxena)
A matrix space is a (vector) subspace of all "n x n" matrices over a given field. As input, one is usually given a set of matrices which span the matrix space under consideration. Then the commutative rank of this matrix space is defined as the maximum rank of any matrix in it.
We consider the problem of commutative rank computation of a given matrix space. The problem is fundamental, as it generalizes several computational problems from algebra and combinatorics. For instance, checking if the commutative rank of the space is n, subsumes problems such as testing perfect matching in graphs and identity testing of algebraic branching programs. An efficient deterministic computation of the commutative rank is a major open problem, although there is a simple and efficient randomized algorithm for it. Recently, there has been a series of results on computing the non-commutative rank of matrix spaces in deterministic polynomial time. Since the non-commutative rank of any matrix space is at most twice the commutative rank, one immediately gets a deterministic 1/2-approximation algorithm for the computation of the commutative rank.
We present a deterministic PTAS for computing the commutative rank of a given matrix space. Although the analysis of our algorithm uses the algebraic tool called "Wong sequences", algorithm itself is a very simple greedy algorithm.
This is a joint work with Prof. Markus Bläser and Anurag Pandey.
We study a very simple model of computation, namely the sum of powers of linear forms. We give exact bounds on the size of these circuits computing monomials. This model of computation has been studied by mathematicians and the size of such circuits is called the Waring rank. The bounds we prove were already known in this literature, however, we reprove them using simple linear algebra and counting.
This is a joint work with Nikhil Balaji, Sai Sandeep and Srikanth Srinivasan.
In the setting of non-commutative arithmetic computations, we define a class of circuits that generalize algebraic branching programs (ABP). This model is called unambiguous because it captures the polynomials in which all monomials are computed in a similar way (that is, all the parse trees are isomorphic). We show that unambiguous circuits of polynomial size can compute polynomials that require ABPs of exponential size, and that they are incomparable with skew circuits. Generalizing a result of Nisan [17] on ABPs, we provide an exact characterization of the complexity of any polynomial in our model. We use it to prove exponential lower bounds for explicit polynomials such as the determinant and to obtain polynomial identity testing results.
We show that the black-box polynomial identity testing for non-commutative polynomials over $n$ variables, degree $D$, and sparsity $t$ can be done in randomized $poly(n,log t,log D)$ time.
As a consequence, if the black-box contains a circuit $C$ of size $s$ computing a polynomial which has at most $t$ non-zero monomials, then the identity testing can be done by a randomized algorithm with running time polynomial in $s$ and $n$ and $log t$. This makes significant progress on a question that has been open for over ten years.
The earlier result by Bogdanov and Wee \cite{BW05}, using the classical Amitsur-Levitzki theorem, gives a randomized polynomial-time algorithm only for circuits of polynomially bounded syntactic degree. In our result, we place no restriction on the degree of the circuit.
This is a joint work with V. Arvind (IMSc) and Raja S. (CMI).
Let M_1, M_2, ... M_s be matrices whose entries are linear forms in variables x_1, x_2, ... , x_n. Given the product M = M_1*M_2*...*M_s, can we reconstruct the M_i's? While this problem seems hard in general, we show that the M_i's can be reconstructed in certain special cases.
Joint work with Neeraj Kayal, Chandan Saha, Sebastien Tavenas
It is known that over fields of large size, any homogeneous degree $d$ polynomial $f$ computed by an arithmetic circuit of size $s$ can be computed by depth five circuits with sum and powering gates of size $2^{\sqrt{n \log d \log s \log n}}$.
In this talk we will focus on depth five circuits with sum and powering gates. We show that any $\Sigma\wedge\Sigma^{2^{o{\sqrt{n}}}}\wedge^{\ge \sqrt{n}}\Sigma$ arithmetic circuit computing the product of variables $x_1\cdots x_n$ requires a top fan-in of $2^{\Omega(n)}$. Our proof involves upper bounding the dimension of projected multilinear derivatives of powers of projections of power symmetric polynomials.
This is a joint work with Christian Engels and Karteek Sreenivasaiaih.
We show that there are explicit polynomials computed by small homogeneous depth-5 arithmetic circuits such that any homogeneous depth-4 circuit must require n^{Omega(sqrt(d))} size, provided d = O(log^2 n). The structure of our explicit polynomial also allows us to show that it can be computed by a small non-homogeneous depth-3 circuit, thereby giving a separation between non-homogeneous depth-3 circuits and homogeneous depth-4 circuits.
The proof involves revisiting a measure introduced by Kayal-Limaye-Saha-Srinivasan of “shifted projected partials” (instead of the more vogue “projected shifted partials”), which was used by them to prove super-polynomial lower bounds for homogeneous depth-4 circuits computing Det_n.
This is joint work with Mrinal Kumar.
The motivation for this work comes from two problems: (1) test algebraic independence of arithmetic circuits over a field of small characteristic, and (2) generalize the structural property of algebraic dependence used by (Kumar, Saraf CCC'16) to arbitrary fields.
It is known that in the case of zero, or large characteristic, using a classical criterion based on the Jacobian, we get a randomized poly-time algorithm to test algebraic independence. Over small characteristic, the Jacobian criterion fails and there is no subexponential time algorithm known. This problem could well be conjectured to be in RP, but the current best algorithm puts it in NP^#P (Mittmann, Saxena, Scheiblechner Trans.AMS'14). Currently, even the case of two bivariate circuits over F_2 is open. We come up with a natural generalization of Jacobian criterion, that works over all characteristic. The new criterion is efficient if the underlying inseparable degree is promised to be a constant. This is a modest step towards the open question of fast independence testing, over finite fields, posed in (Dvir, Gabizon, Wigderson FOCS'07).
In a set of linearly dependent polynomials, any polynomial can be written as a linear combination of the polynomials forming a basis. The analogous property for algebraic dependence is false, but a property approximately in that spirit is named as "functional dependence" in (Kumar, Saraf CCC'16) and proved for zero or large characteristic. We show that functional dependence holds for arbitrary fields, thereby answering the open questions in (Kumar, Saraf CCC'16). Following them we use the functional dependence lemma to prove the first exponential lower bound for locally low algebraic rank circuits for arbitrary fields (a model that strongly generalizes homogeneous depth-4 circuits). We also recover their quasipoly-time hitting-set for such models, for fields of characteristic smaller than the ones known before.
(based on joint work with Anurag Pandey & Amit Sinhababu. MFCS'16)
We give the first separation between the power of *formulas* and *circuits* of a given depth in the \AC^0[\oplus] basis (unbounded fan-in AND, OR, NOT and MOD_2 gates). Our main result shows that, for all d(n) \le O(\frac{\log n}{\log\log n}), there exist polynomial-size depth-d circuits that are not equivalent to any depth-d formulas of size n^{o(d)} (moreover, this separation is optimal in that n^{o(d)} cannot be improved to n^{O(d)}). The result is obtained by a combination of new lower and upper bounds for the class of {\em Approximate Majorities}, that is, defined as Boolean functions {0,1}^n to {0,1} that agree with the Majority function on 3/4 fraction of inputs.
Joint work with Benjamin Rossman (University of Toronto).
Consider the problem of determining if for a given tuple of n by n matrices (X_1, X_2,..,X_m) there are subspaces V, W of C^n such that the images X_1(V), X_2(V), .., X_m(V) are all contained in W and dim(W) < dim(V)? This problem of determining if a tuple (X_1,X_2,..,X_m) compresses some subspace of C^n has connections to invariant theory and non commutative rank of matrices. We review some recent progress on this problem, a polynomial time algorithm due to Garg et al (GGOW, FOCS 2016) and also due to Ivanyos et al (IQS, Computational Complexity). We will present the algorithm of Garg et al.
We will then introduce the Brascamp-Lieb inequalities, and review some recent progress on the algorithmic aspects of these inequalities due to Garg et al, (GGOW, STOC17).
This talk presents a framework of "algebraically natural lower bounds" for algebraic circuits, which is similar to the natural proofs notion of Razborov and Rudich for boolean circuit lower bounds, and captures nearly all lower bound techniques known. However, unlike the boolean setting, there has been little concrete evidence demonstrating that this is a barrier to obtaining super-polynomial lower bounds for general algebraic circuits.
We show that the existence of an algebraic natural proofs barrier is equivalent to the existence of succinct derandomization of the polynomial identity testing problem. That is, whether the coefficient vectors of polylog(N)-degree polylog (N)-size circuits is a hitting set for the class of poly(N)-degree poly(N)-size circuits. Further, we give an explicit universal construction showing that if such a succinct hitting set exists, then our universal construction suffices.
We assess the existing literature constructing hitting sets for restricted classes of algebraic circuits and modify some of these constructions to obtain succinct hitting sets, thus suggesting evidence supporting the existence of an algebraic natural proofs barrier.
Our framework is similar to the Geometric Complexity Theory (GCT) program of Mulmuley and Sohoni, except that here we emphasize constructiveness of the proofs while the GCT program emphasizes symmetry. Nevertheless, our succinct hitting sets have relevance to the GCT program as they imply lower bounds for the complexity of the defining equations of polynomials computed by small circuits.
(Joint work with Michael Forbes and Amir Shpilka)