Progress on Polynomial Identity Testing - II

2014/01/06 by Nitin Saxena, Saxena, Nitin · 6 citations
Computer Science · Mathematics · #12Y05 #13P25 #68Q25 #68W30 #Algebraic Geometry (math.AG) #Commutative Algebra (math.AC) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #cs.DM #math.AC #math.AG #msc:12Y05 #msc:13P25 #msc:68Q25 #msc:68W30

paper · pdf · doi:10.48550/arxiv.1401.0976

17 pages, 1 figure, survey

arxiv created 2014/01/06 · arxiv updated 2014/01/07

Abstract

We survey the area of algebraic complexity theory; with the focus being on the problem of polynomial identity testing (PIT). We discuss the key ideas that have gone into the results of the last few years.

Cited by

• Quantum automated theorem proving
• Efficient Polynomial Identity Testing Over Nonassociative Algebras
• Identity Testing for Circuits with Exponentiation Gates
• Algebraic Pseudorandomness in VNC⁰
• Deterministic Depth-4 PIT and Normalization
• Rank Bounds and PIT for Σ³ ΠΣΠ^d circuits via a non-linear Edelstein-Kelly theorem

Related

• Shallow Circuits with High-Powered Inputs
• Efficient Polynomial Identity Testing Over Nonassociative Algebras
• New results on Noncommutative and Commutative Polynomial Identity Testing
• The Power of Depth 2 Circuits over Algebras
• A hitting set construction, with application to arithmetic circuit lower bounds