ICTS

A useful corollary of the famous Sylvester-Gallai theorem, which found many applications in theoretical computer science, states that if a finite set of linear forms L satisfy that for every two forms, L1, L2 ∈ L there is a subset I ⊂ L, such that L1, L2 ∈ I / and whenever L1 and L2 vanish then also ∏i∈I Li vanishes, then the linear span of L has dimension at most 3. This corollary is used to achieve deterministic algorithms for certain depth-3 polynomial identities and to bound performance of locally correctable codes. In this work we prove that if a finite set of irreducible quadratic polynomials Q satisfy that for every two polynomials Q1, Q2 ∈ Q there is a subset I ⊂ Q, such that Q1, Q2 ∈ I / and whenever Q1 and Q2 vanish then also ∏i∈I Qi vanishes, then the linear span of the polynomials in Q has dimension O(1). This extended an earlier result by [Shp18], that showed a similar conclusion when |I| = 1. This result brings us one step closer towards obtaining a polynomial time deterministic algorithm for the polynomial identity question of certain depth-4 identities. To obtain our main theorem we prove a new result classifying the possible ways that a product of quadratic polynomials ∏i Qi can vanish when two other quadratic polynomials vanish.

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any nonzero polynomial f(x1,...,xn) of degree at most s will evaluate to a nonzero value at some point on an n-dimensional grid S^n with side length |S| > s . This gives an explicit hitting set for all n-variate degree s, size s algebraic circuits of size (s+1)^n. We prove the following results: - Let eps > 0 be a constant. For a sufficiently large constant n and all s >= n, if we have an explicit hitting set of size (s+1)^{n - eps} for the class of n-variate degree s polynomials that are computable by algebraic circuits of size s, then for all large s, we have an explicit hitting set of size s^{exp(exp(O(log*s)))} for s-variate circuits of degree s and size s. That is, if we can obtain a barely non-trivial exponent compared to the trivial (s+1)^n sized hitting set even for constant variate circuits, we can get an almost complete derandomization of PIT. - The above result holds when "circuits" are replaced by "formulas" or "algebraic branching programs". This extends a recent surprising result of Agrawal, Ghosh and Saxena (STOC 2018) who proved the same conclusion for the class of algebraic circuits, if the hypothesis provided a hitting set of size at most (s^{n^{0.5 - eps}}) (where eps > 0 is any constant). Hence, our work significantly weakens the hypothesis of Agrawal, Ghosh and Saxena to only require a slightly non-trivial saving over the trivial hitting set, and also presents the first such result for algebraic branching programs and formulas. This is joint work with Mrinal Kumar and Ramprasad Saptharishi.

In a Nisan-Wigderson design polynomial, denoted NW, every pair of monomials has few variables in common and this property has been used in recent years to prove lower bounds for several classes of arithmetic circuits. But unlike other well known polynomial families, like the Permanent, the Determinant and the iterated matrix multiplication polynomials, many natural questions on the design polynomial family are open. Some of them are as follows: * Is the design polynomial family VNP complete? * What is the structure of the group of symmetries of NW? * Is NW characterized by its symmetries over the complex field, real field and finite fields? * Given an arithmetic circuit C, can we efficiently test if C computes NW? * Given oracle access to a polynomial f, can we determine efficiently if f is equivalent to NW, i.e. if f = NW(AX) for some invertible matrix A, where X is a column vector of variables. * Given a point v in the Boolean hypercube, can it be checked efficiently if NW(v)=0? In this talk, we would discuss answers to a few of these questions. Joint work with Chandan Saha.

It is a fundamental problem in the study of computational complexity to understand if access to more resources would mean strictly more computational power. In classical complexity, we have seen such examples in terms of Time Hierarchy and Space Hierarchy theorems. Here, time and space are the resources. It is natural to ask such a question in the setting of algebraic complexity setting. Here, access to more resources translates to allowing the model to perform more number of operations which in turn is allowing the "algebraic formulas" to have larger size.

Arithmetic formulas are directed trees where the leaves are labelled by variables and elements of the field, and internal vertices are labelled by + or x. Every internal vertex computes a polynomial by operating on its inputs. It is easy to see that they are a natural model of computation of polynomials, syntactically (symbolically). The size of the arithmetic formulas refers to the number of + and x operations needed to compute the polynomial. Rephrasing the question in the algebraic setting we ask the following: for any s, \varepsilon >0, are there polynomial computations that can be efficiently computed by arithmetic formulas of size s but not by any arithmetic formula of size s^{1-\varepsilon}?

In this talk, we will restrict ourselves to arithmetic formulas where computation at every vertex is a multilinear polynomial and here we show explicit separations between the expressive powers of multilinear formulas of small-depth and all polynomial sizes. The multilinear restriction is a reasonable one since most polynomials of interest are indeed multilinear. Formally, we will show that for any s = poly(n) and \delta > 0, we show that there are explicit polynomial families that have multilinear formulas of size at most s but no 'small'-depth multilinear formulas of size less than s^{0.5 - \delta}. Our proof can be viewed as a derandomization of a lower bound technique of Raz (JACM 2009) using \epsilon-biased spaces. (Joint work with Nutan Limaye and Srikanth Srinivasan. Appeared in the proceedings of ICALP 2018.)

It is a long-standing open problem in computer algebra to find a deterministic polynomial-time algorithm that factorizes a given univariate polynomial $f(X)$ over a finite field $\mathbb{F}_p$. Such an algorithm is not known even under the generalized Riemann hypothesis (GRH). In this talk, I will discuss a unifying approach for this problem based on a family of combinatorial objects called P-schemes. Our approach subsumes known GRH-based results and also leads to some new results. In particular, we show how to beat Evdokimov's algorithm when a polynomial $\tilde{f}(X)\in \mathbb{Z}[X]$ lifting $f(X)$ is given whose Galois group has a "linear" structure.

Computing the (real) roots of polynomial is an important problem in mathematics and theoretical computer science. We propose an efficient algorithm to compute the real roots of a sparse polynomial having $k$ non-zero real-valued coefficients. It is known that even for 4-nomials, one can not hope for a polynomial (in the input size) time algorithm for isolating the real roots. Therefore we propose a slightly relaxed notion of isolation of real roots. For a given positive integer $L$, our algorithm returns disjoint disks $D_1,D_2,...,D_s$ with $s<2k$, centered at the real axis and of radius less than $2^{-L}$ together with positive integers $u_1,...,u_s$ such that each disk $D_i$ contains exactly $u_i$ roots of $f$ counted with multiplicity. In addition, it is ensured that each real root of $f$ is contained in one of the disks. If $f$ has only simple real roots, our algorithm can also be used to isolate all real roots.The bit complexity of our algorithm is polynomial in $k$ and $\log(n)$,and near-linear in $L$ and $\tau$, where $2^{-\tau}$ and $2^{\tau}$ constitute lower and upper bounds on the absolute values of the non-zero coefficients of $f$, and $n$ is the degree of $f$. For root isolation, the bit complexity is polynomial in $k$ and $\log(n)$, and near-linear in $\tau$ and $\log(1/\sigma)$, where $\sigma$ denotes the separation of the real roots. We also show that the roots of integer trinomials are well separated (this was also independently proved by Koiran). By using our algorithm, it follows that the real roots of trinomials can be isolated in polynomial time. This is a joint work with Prof. Michael Sagraloff( Max-Planck-Institut für Informatik and University of Applied Sciences Landshut).