The complexity of two problems on arithmetic circuits

DOI10.1016/J.TCS.2007.08.008zbMATH Open1154.68564OpenAlexW2053392671MaRDI QIDQ2465637FDOQ2465637

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

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
• Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials

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)

Cites Work

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

Cited In (13)

• Arithmetization: A new method in structural complexity theory
• The Complexity of theA B CProblem
• Title not available (Why is that?)
• Arithmetic complexity in ring extensions
• Title not available (Why is that?)
• On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
• Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials
• Monomials in arithmetic circuits: complete problems in the counting hierarchy
• Monomials in arithmetic circuits: complete problems in the counting hierarchy
• The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
• Boolean circuits versus arithmetic circuits
• A case of depth-3 identity testing, sparse factorization and duality
• Monomials, multilinearity and identity testing in simple read-restricted circuits

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)