Some complete and intermediate polynomials in algebraic complexity theory

DOI10.1007/s00224-016-9740-yzbMath1393.68079arXiv1603.04606OpenAlexW2592308996MaRDI QIDQ1635814

Meena Mahajan, Nitin Saurabh

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

zbMATH Keywords

completenesshomomorphismstree decompositionlower boundsextension complexitymonotone projectionsVBPVNP-intermediateVP

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) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25)

Related Items (6)

A note on VNP-completeness and border complexity ⋮ Some complete and intermediate polynomials in algebraic complexity theory ⋮ On the relative power of reduction notions in arithmetic circuit complexity ⋮ Monotone arithmetic complexity of graph homomorphism polynomials ⋮ Complexity classes and completeness in algebraic geometry ⋮ Variants of the determinant polynomial and the \textsf{VP}-completeness

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