Tag - Complexity theory

For a matrix with entries given by multivariate polynomials (over a field F) of degrees bounded by a constant d, a problem of interest is to find its rank over F(x₁,...,x_n). The problem seems to be of fundamental nature, as it generalizes several computational problems arising in algebra, geometry, and combinatorics. For instance, when the entries are given by homogeneous linear forms, this rank computation problem already captures the problems like testing for perfect matching in graphs, and identity testing for algebraic branching programs. Its higher degree cases capture more general problems of algebro-geometric nature, like testing algebraic independence of polynomials using the Jacobian matrix, and finding the dimension of the dual varieties of hypersurfaces using the Hessian matrix.

Although the problem has a simple and efficient randomized algorithm using the Schwartz-Zippel lemma, an efficient deterministic computation of the rank is a major open problem, since a deterministic algorithm for exactly computing the rank in the linear case is already equivalent to the celebrated Polynomial Identity Testing (PIT) problem which itself would imply circuit complexity lower bounds (Kabanets-Impagliazzo '03).

In this talk, we will see a simple deterministic algorithm for computing the rank up to a factor of (1 - ε), which runs in polynomial time (i.e. we give a PTAS) when ε and d are constants.

We consider the problem of constructing explicit matrices which cannot be expressed as a product of a few sparse matrices. In addition to being a natural mathematical question, this problem appears in various incarnations in computer science. In the talk we will survey the background and motivation, prove some lower bounds, and present the main open problems.

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.

Geometric Complexity Theory as initiated by Mulmuley and Sohoni in two papers (SIAM J Comput 2001, 2008) aims to separate algebraic complexity classes via representation theoretic multiplicities in coordinate rings of specific group varieties. The papers also conjecture that the vanishing behavior of these multiplicities would be sufficient to separate complexity classes (so-called occurrence obstructions). The existence of such strong occurrence obstructions has been recently disproven in 2016 in two successive papers, Ikenmeyer-Panova (Adv. Math.) and Bürgisser-Ikenmeyer-Panova (J. AMS). This raises the question whether separating group varieties via representation theoretic multiplicities is stronger than separating them via occurrences. This paper provides for the first time a setting where separating with multiplicities can be achieved, while the separation with occurrences is provably impossible. Our setting is surprisingly simple and natural: We study the variety of products of homogeneous linear forms (the so-called Chow variety) and the variety of polynomials of bounded border Waring rank (i.e. a higher secant variety of the Veronese variety).

The talk is an introduction to geometric complexity theory, which is an approach towards complexity lower bounds in algebraic complexity theory that was initiated by Mulmuley and Sohoni in 2001. I define the basic notions from algebraic geometry, representation theory, and algebraic combinatorics, and state some fundamental open problems and remark on some recent progress.

Derandomization of blackbox identity testing reduces to extremely special circuit models. After a line of work, it is known that focusing on circuits with constant-depth and constantly many variables is enough (Agrawal, Ghosh, Saxena) to get to general hitting-sets and circuit lower bounds. This inspires us to study circuits with few variables, eg. logarithmic in the size s.

We give the first poly(s)-time blackbox identity test for size s and n=O(logs) variate depth-3 diagonal circuits (or Σ∧Σⁿ). The former model is well-studied but no poly(s2ⁿ)-time identity test was known before us. We introduce the concept of cone-closed basis isolation and prove its usefulness in studying log-variate circuits. It subsumes the previous notions of rank-concentration studied extensively in the context of ROABP models.

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any nonzero polynomial f(x₁,...,x_n) of degree at most s will evaluate to a non-zero value at some point on an n-dimensional grid Sⁿ 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)ⁿ. We prove the following results:

- Let ε > 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-ε 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)ⁿ 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 who proved the same conclusion for the class of algebraic circuits, if the hypothesis provided a hitting set of size at most (s^n0.5-ε) (where ε > 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.

Polynomial factorization is one of the fundamental questions in algebraic complexity. Given a multivariate polynomial f in the form of a succinct representation (e.g., arithmetic circuit), the task is finding a succinct representation for its factors. In addition to being a natural question, polynomial factorization has many applications such as hardness versus randomness and decoding Reed-Solomon codes.

An arithmetic circuit class C is closed under factor if the following holds: let f be a polynomial in class C, then its factors also lie in C. In this talk, I’m going to focus on two recent closure results in polynomial factorization. The first one is for constant depth arithmetic circuits of poly-logarithmic degree and the second one is for VNP. Some applications of these results and future direction will also be discussed.

We will discuss a short and self contained proof (based on joint work with Chi-Ning Chou and Noam Solomon) of a classical result of Kaltofen from the mid 1980s where he showed that if an n-variate degree-d polynomial f can be computed by an arithmetic circuit of size s, then each of its factors can be computed by an arithmetic circuit of size at most poly(s,n,d).

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, L₁, L₂ ∈ L there is a subset I ⊂ L, such that L₁, L₂ ∈ I and whenever L₁ and L₂ vanish then also ∏_i∈I L_i 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 Q₁,Q₂ ∈ Q there is a subset I ⊂ Q, such that Q₁,Q₂ ∈ I and whenever Q₁ and Q₂ vanish then also ∏_i∈I Q_i vanishes, then the linear span of the polynomials in Q has dimension O(1). This extended an earlier result, 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 Q_i can vanish when two other quadratic polynomials vanish.