Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems

DOI10.1007/978-3-642-22006-7_59zbMath1333.68119OpenAlexW1232310145MaRDI QIDQ3012844

Stefan Mengel

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_59

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The arithmetic complexity of tensor contraction ⋮ Some complete and intermediate polynomials in algebraic complexity theory ⋮ The complexity of weighted counting for acyclic conjunctive queries ⋮ Unnamed Item ⋮ Algebraic Complexity Classes ⋮ Variants of the determinant polynomial and the \textsf{VP}-completeness

Cites Work

• On the expressive power of CNF formulas of bounded tree- and clique-width
• Completeness and reduction in algebraic complexity theory
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Characterizing Valiant's algebraic complexity classes
• Parametrized complexity theory.
• On the Desirability of Acyclic Database Schemes
• Fast Parallel Computation of Polynomials Using Few Processors
• A Dichotomy Theorem for Polynomial Evaluation
• The complexity of acyclic conjunctive queries
• Computing Algebraic Formulas Using a Constant Number of Registers
• On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
• The complexity of satisfiability problems
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic