The complexity of two problems on arithmetic circuits

DOI10.1016/j.tcs.2007.08.008zbMath1154.68564MaRDI QIDQ2465637

Sylvain Perifel, Pascal Koiran

Publication date: 7 January 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.08.008

zbMATH Keywords

algorithms; polynomials; arithmetic circuits; counting classes

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W30: Symbolic computation and algebraic computation

68W05: Nonnumerical algorithms

Related Items

On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1, A case of depth-3 identity testing, sparse factorization and duality, Monomials in arithmetic circuits: complete problems in the counting hierarchy, Monomials, multilinearity and identity testing in simple read-restricted circuits

Cites Work

• Unnamed Item
• The complexity of computing the permanent
• Strong nondeterministic polynomial-time reducibilities
• Completeness and reduction in algebraic complexity theory
• On Defining Integers in the Counting Hierarchy and Proving Arithmetic Circuit Lower Bounds
• On the Complexity of Numerical Analysis
• Greatest common divisors of polynomials given by straight-line programs
• Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
• The Complexity of Enumeration and Reliability Problems
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• Characterizing Valiant’s Algebraic Complexity Classes
• Counting classes: Thresholds, parity, mods, and fewness
• Derandomizing polynomial identity tests means proving circuit lower bounds
• The complexity theory companion