Pascal Koiran
Shallow Circuits with High-Powered Inputs.
Thu, 07/29/2010 - 15:01 — SomNambulAuthors: Pascal Koiran
Subjects: Computational Complexity
AbstractA polynomial identity testing algorithm must determine whether an input
polynomial (given for instance by an arithmetic circuit) is identically equal
to 0. In this paper, we show that a deterministic black-box identity testing
algorithm for (high-degree) univariate polynomials would imply a lower bound on
the arithmetic complexity of the permanent. The lower bounds that are known to
follow from derandomization of (low-degree) multivariate identity testing are
weaker.Symmetric Determinantal Representation of Formulas and Weakly Skew Circuits.
Fri, 07/23/2010 - 15:01 — SomNambulAuthors: Bruno Grenet, Pascal Koiran, Natacha Portier, Erich Kaltofen
Subjects: Computational Complexity
AbstractWe deploy algebraic complexity theoretic techniques for constructing
symmetric determinantal representations of formulas and weakly skew circuits.
Our representations produce matrices of much smaller dimensions than those
given in the convex geometry literature when applied to polynomials having a
concise representation (as a sum of monomials, or more generally as an
arithmetic formula or a weakly skew circuit). These representations are valid
in any field of characteristic different from 2.Arithmetic circuits: the chasm at depth four gets wider.
Fri, 06/25/2010 - 15:02 — SomNambulAuthors: Pascal Koiran
Subjects: Computational Complexity
AbstractIn their paper on the ``chasm at depth four'', Agrawal and Vinay have shown
that polynomials in m variables of degree O(m) which admit arithmetic circuits
of size 2^o(m) also admit arithmetic circuits of depth four and size 2^o(m).
This theorem shows that for problems such as arithmetic circuit lower bounds or
black-box derandomization of identity testing, the case of depth four circuits
is in a certain sense the general case. In this paper we show that smaller
depth four circuits can be obtained if we start from polynomial size arithmetic
circuits.A Dichotomy Theorem for Polynomial Evaluation.
Wed, 12/16/2009 - 16:01 — SomNambulAuthors: Pascal Koiran, Irénée Briquel
Subjects: Computational Complexity
AbstractA dichotomy theorem for counting problems due to Creignou and Hermann states
that or any nite set S of logical relations, the counting problem #SAT(S) is
either in FP, or #P-complete. In the present paper we show a dichotomy theorem
for polynomial evaluation. That is, we show that for a given set S, either
there exists a VNP-complete family of polynomials associated to S, or the
associated families of polynomials are all in VP.The multivariate resultant lies between NP and AM.
Tue, 12/15/2009 - 16:01 — SomNambulAuthors: Bruno Grenet, Pascal Koiran, Natacha Portier
Subjects: Computational Complexity
AbstractThe resultant of a square system of homogeneous polynomials is a polynomial
in their coefficients which vanishes whenever the system has a solution. Canny
gave an algorithm running in polynomial space to compute it but no lower bound
was known. We investigate the complexity of the associated decision problem and
give a hardness result: Testing the resultant for zero lies in the class
Arthur-Merlin and is NP-hard. We give a randomized reduction and a
deterministic reduction for NP-hardness. The latter can be seen as a
derandomization result.A hitting set construction, with application to arithmetic circuit lower bounds.
Wed, 12/09/2009 - 16:01 — SomNambulAuthors: Pascal Koiran
Subjects: Computational Complexity
AbstractA polynomial identity testing algorithm must determine whether a given input
polynomial is identically equal to 0. We give a deterministic black-box
identity testing algorithm for univariate polynomials of the form $\sum_{j=0}^t
c_j X^{\alpha_j} (a + b X)^{\beta_j}$. From our algorithm we derive an
exponential lower bound for representations of polynomials such as
$\prod_{i=1}^{2^n} (X^i-1)$ under this form. It has been conjectured that these
polynomials are hard to compute by general arithmetic circuits.
User login
