A Dichotomy Theorem for Polynomial Evaluation

DOI10.1007/978-3-642-03816-7_17zbMath1250.68123OpenAlexW1957065512MaRDI 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

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)

Related Items (6)

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

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

This page was built for publication: A Dichotomy Theorem for Polynomial Evaluation