A Dichotomy Theorem for Polynomial Evaluation

DOI10.1007/978-3-642-03816-7_17zbMath1250.68123MaRDI QIDQ3182924

Irenée Briquel, Pascal Koiran

Publication date: 16 October 2009

Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

On the relative power of reduction notions in arithmetic circuit complexity, Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs, Algebraic Complexity Classes, Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems, A Dichotomy Theorem for Polynomial Evaluation

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• On the algebraic complexity of some families of coloured Tutte polynomials
• Completeness and reduction in algebraic complexity theory
• The vertex-cover polynomial of a graph
• Complexity of generalized satisfiability counting problems
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• A Dichotomy Theorem for Polynomial Evaluation
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Hard Enumeration Problems in Geometry and Combinatorics
• The Complexity of Enumeration and Reliability Problems
• #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
• The complexity of satisfiability problems