The complexity of two problems on arithmetic circuits

DOI10.1016/J.TCS.2007.08.008MaRDI QIDQ2465637zbMATH OpenOpenAlexFDO

Authors Pascal Koiran, Sylvain Perifel

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

algorithmsarithmetic circuitspolynomialscounting classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Nonnumerical algorithms (68W05)

Recommendations

• Monomials in arithmetic circuits: complete problems in the counting hierarchy
• Monomials in arithmetic circuits: complete problems in the counting hierarchy
• Monomials, multilinearity and identity testing in simple read-restricted circuits
• Depth-3 arithmetic circuits over fields of characteristic zero

Cites work

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

Cited in

(12)

• Monomials, multilinearity and identity testing in simple read-restricted circuits
• Arithmetization: A new method in structural complexity theory
• The Complexity of theA B CProblem
• A case of depth-3 identity testing, sparse factorization and duality
• Monomials in arithmetic circuits: complete problems in the counting hierarchy
• scientific article; zbMATH DE number 953031 (Why is no real title available?)
• scientific article; zbMATH DE number 7155168 (Why is no real title available?)
• The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
• On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
• Monomials in arithmetic circuits: complete problems in the counting hierarchy
• Boolean circuits versus arithmetic circuits
• Arithmetic complexity in ring extensions

This page was built for publication: The complexity of two problems on arithmetic circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2465637)