Deterministic polynomial identity testing in non-commutative models (Q1781113): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
 
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/s00037-005-0188-8 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2121894367 / rank
 
Normal rank

Latest revision as of 00:42, 20 March 2024

scientific article
Language Label Description Also known as
English
Deterministic polynomial identity testing in non-commutative models
scientific article

    Statements

    Deterministic polynomial identity testing in non-commutative models (English)
    0 references
    0 references
    0 references
    16 June 2005
    0 references
    The authors give a deterministic polynomial time algorithm for zero testing of polynomials in non-commutative variables given by arithmetic formulae. A similar deterministic algorithm determines in polynomial time whether or not the output of a pure set-multilinear arithmetic circuit is identically 0. It is also proved that any pure circuit computing the permanent or the determinant of an \(n\times n\)-matrix has size \(2^{\Omega (n)}\). The proofs are based on the partial derivative method introduced by \textit{N. Nisan} and \textit{A. Wigderson} [Comput. Complexity 6, 217--234 (1997; Zbl 0890.68074)]. The idea is that the space spanned by all partial derivatives of a non-commutative polynomial \(f\) is of small dimension, provided that \(f\) is computed by a small arithmetic formula. A procedure to recursively check whether or not the relevant partial derivatives are identically 0 is also needed. Similar techniques have been already used by \textit{S. Waack} [``On the descriptive and algorithmic power of parity ordered binary decision diagrams'', Lect. Notes Comput. Sci. 1200, 201--212 (1997)].
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    polynomial identity testing
    0 references
    non-commutative formulae
    0 references
    arithmetic branching programs
    0 references
    0 references