Progress on Polynomial Identity Testing - II

2014/01/06 by Saxena, Nitin · 2 citations
#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

paper · doi:10.48550/arxiv.1401.0976

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

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