Deterministic polynomial identity testing in non commutative models

Ran Raz, Amir Shpilka

Research output: Contribution to journalConference article

10 Scopus citations

Abstract

We give a deterministic polynomial time algorithm for polynomial identity testing in the following two cases: 1. Non Commutative Arithmetic Formulas: The algorithm gets as an input an arithmetic formula in the non-commuting variables x1,...,xn and determines whether or not the output of the formula is identically 0 (as a formal expression). 2. Pure Arithmetic Circuits: The algorithm gets as an input a pure arithmetic circuit (as defined by Nisan and Wigderson [3]) in the variables x1,...,xn and determines whether or not the output of the circuit is identically 0 (as a formal expression). We also give a deterministic polynomial time identity testing algorithm for non commutative algebraic branching programs as defined by Nisan [2]. One application is a deterministic polynomial time identity testing for multilinear arithmetic circuits of depth 3. Finally, we observe an exponential lower bound for the size of pure arithmetic circuits for the permanent and for the determinant. (Only lower bounds for the depth of pure circuits were previously known [3]).

Original languageEnglish (US)
Pages (from-to)215-222
Number of pages8
JournalProceedings of the Annual IEEE Conference on Computational Complexity
Volume19
StatePublished - Oct 18 2004
Externally publishedYes
EventProceedings - 19th IEEE Annual Conference on Computational Complexity - Amherst, MA, United States
Duration: Jun 21 2004Jun 24 2004

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Deterministic polynomial identity testing in non commutative models'. Together they form a unique fingerprint.

  • Cite this