Monomials in arithmetic circuits: complete problems in the counting hierarchy
From MaRDI portal
Publication:2353185
DOI10.1007/s00037-013-0079-3zbMath1331.68085arXiv1110.6271OpenAlexW2134214111MaRDI QIDQ2353185
Hervé Fournier, Guillaume Malod, Stefan Mengel
Publication date: 8 July 2015
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1110.6271
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)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On enumerating monomials and other combinatorial structures by polynomial interpolation
- Interpolation in Valiant's theory
- On defining integers and proving arithmetic circuit lower bounds
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Interpolation of polynomials given by straight-line programs
- The complexity of combinatorial problems with succinct input representation
- Feasible arithmetic computations: Valiant's hypothesis
- Properties that characterize LOGCFL
- A probabilistic remark on algebraic program testing
- Completeness and reduction in algebraic complexity theory
- Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials
- The complexity of matrix rank and feasible systems of linear equations
- The complexity of two problems on arithmetic circuits
- The complexity of membership problems for circuits over sets of natural numbers
- Characterizing Valiant's algebraic complexity classes
- Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs
- Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth
- The Complexity of Finding kth Most Probable Explanations in Probabilistic Networks
- Complexity of finite-horizon Markov decision process problems
- Faster Algebraic Algorithms for Path and Packing Problems
- On the Complexity of Numerical Analysis
- A New Pebble Game that Characterizes Parallel Complexity Classes
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- On the power of deterministic reductions to C=P
- Complexity classes defined by counting quantifiers
- Randomness efficient identity testing of multivariate polynomials
- The Complexity of Testing Monomials in Multivariate Polynomials
- Computational Complexity
- Algebraic independence in positive characteristic: A $p$-adic calculus
- Derandomizing polynomial identity tests means proving circuit lower bounds
- The complexity theory companion
This page was built for publication: Monomials in arithmetic circuits: complete problems in the counting hierarchy
