Some complete and intermediate polynomials in algebraic complexity theory
Publication:1635814
DOI10.1007/s00224-016-9740-yzbMath1393.68079arXiv1603.04606OpenAlexW2592308996MaRDI QIDQ1635814
Publication date: 1 June 2018
Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1603.04606
completenesshomomorphismstree decompositionlower boundsextension complexitymonotone projectionsVBPVNP-intermediateVP
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) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25)
Related Items (6)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of counting homomorphisms seen from the other side
- On the extension complexity of combinatorial polytopes
- Turing machines that take advice
- Lower bounds on monotone complexity of the logical permanent
- The monotone circuit complexity of Boolean functions
- On the complexity of H-coloring
- Feasible arithmetic computations: Valiant's hypothesis
- The complexity of partial derivatives
- Treewidth. Computations and approximations
- Completeness and reduction in algebraic complexity theory
- Conjunctive query containment revisited
- Counting \(H-\)colorings of partial \(k-\)trees
- Some complete and intermediate polynomials in algebraic complexity theory
- Cook's versus Valiant's hypothesis
- Unifying known lower bounds via geometric complexity theory
- Characterizing Valiant's algebraic complexity classes
- Dichotomy Theorems for Homomorphism Polynomials of Graph Classes
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- A Dichotomy Theorem for Homomorphism Polynomials
- The arithmetic complexity of tensor contractions
- Homomorphism Polynomials Complete for VP
- Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
- Fast Parallel Computation of Polynomials Using Few Processors
- Arithmetic Circuits: A survey of recent results and open questions
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- On the Structure of Polynomial Time Reducibility
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The Matching Polytope has Exponential Extension Complexity
- Paths, Trees, and Flowers
- Parameterized Algorithms
This page was built for publication: Some complete and intermediate polynomials in algebraic complexity theory