Monomials in arithmetic circuits: complete problems in the counting hierarchy

DOI10.4230/LIPICS.STACS.2012.362zbMATH Open1245.68087MaRDI QIDQ2904776FDOQ2904776

Authors: Stefan Mengel, Hervé Fournier, Guillaume Malod 

Publication date: 23 August 2012

Recommendations

• Monomials in arithmetic circuits: complete problems in the counting hierarchy
• Lower bounds for monotone counting circuits
• The complexity of two problems on arithmetic circuits
• Monomials, multilinearity and identity testing in simple read-restricted circuits
• Algorithms for testing monomials in multivariate polynomials

zbMATH Keywords

arithmetic circuitspolynomialscounting problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (14)

• Evaluating Monotone Circuits on Cylinders, Planes and Tori
• Enumeration of the monomials of a polynomial and related complexity classes
• Identity testing, multilinearity testing, and monomials in read-once/twice formulas and branching programs
• Building above read-once polynomials: identity testing and hardness of representation
• Monomials in arithmetic circuits: complete problems in the counting hierarchy
• Exact Parameterized Multilinear Monomial Counting via k-Layer Subset Convolution and k-Disjoint Sum
• Complexity of certain systems of monomials in calculation by composition circuits
• Algebraic independence in positive characteristic: a \(p\)-adic calculus
• Arithmetic Circuits and Polynomial Replacement Systems
• Algebraic complexity classes
• Monomials, multilinearity and identity testing in simple read-restricted circuits
• The complexity of two problems on arithmetic circuits
• Title not available (Why is that?)
• On enumerating monomials and other combinatorial structures by polynomial interpolation

This page was built for publication: Monomials in arithmetic circuits: complete problems in the counting hierarchy

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