Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Aditya Varre:

TR18-135 | 31st July 2018
Prasad Chaugule, Nutan Limaye, Aditya Varre

Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes

Revisions: 1

We present polynomial families complete for the well-studied algebraic complexity classes VF, VBP, VP, and VNP. The polynomial families are based on the homomorphism polynomials studied in the recent works of Durand et al. (2014) and Mahajan et al. (2016). We consider three different variants of graph homomorphisms, namely injective ... more >>>

ISSN 1433-8092 | Imprint