loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
19th Annual IEEE Conference on Computational Complexity (CCC'04)
Deterministic Polynomial Identity Testing in Non-Commutative Models
Amherst, Massachusetts
June 21-June 24
ISBN: 0-7695-2120-7
ASCII Text
x 
 
Ran Raz, Amir Shpilka, "Deterministic Polynomial Identity Testing in Non-Commutative Models," Computational Complexity, Annual IEEE Conference on, pp. 215-222, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2004.1313845,
author = {Ran Raz and Amir Shpilka},
title = {Deterministic Polynomial Identity Testing in Non-Commutative Models},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2004},
issn = {1093-0159},
pages = {215-222},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313845},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Deterministic Polynomial Identity Testing in Non-Commutative Models
SN - 1093-0159
SP215
EP222
A1 - Ran Raz,
A1 - Amir Shpilka,
PY - 2004
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Ran Raz, Weizmann Institute of Science
Amir Shpilka, Weizmann Institute of Science

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 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]).

    Citation:
    Ran Raz, Amir Shpilka, "Deterministic Polynomial Identity Testing in Non-Commutative Models," ccc, pp.215-222, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004
    Usage of this product signifies your acceptance of the Terms of Use.