scientific article

DOI10.4086/cjtcs.2016.003zbMath1356.68080OpenAlexW4243387057MaRDI QIDQ2808529

Nicolas de Rugy-Altherre, Arnaud Durand, Meena Mahajan, Nitin Saurabh, Guillaume Malod

Publication date: 24 May 2016

Published in: Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/cjtcs.2016.003

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

completenesspolynomialsgraph homomorphismalgebraic complexityVPVNP

Mathematics Subject Classification ID

Graph polynomials (05C31) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

Some complete and intermediate polynomials in algebraic complexity theory ⋮ Monotone arithmetic complexity of graph homomorphism polynomials ⋮ On the closures of monotone algebraic classes and variants of the determinant

Cites Work

• Unnamed Item
• A Dichotomy Theorem for Homomorphism Polynomials
• Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
• Fast Parallel Computation of Polynomials Using Few Processors
• Arithmetic Circuits and Polynomial Replacement Systems

This page was built for publication: