ECCC-Report TR18-135https://eccc.weizmann.ac.il/report/2018/135Comments and Revisions published for TR18-135en-usWed, 12 Jun 2019 09:05:10 +0300
Revision 1
| Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes |
Prasad Chaugule,
Nutan Limaye,
Aditya Varre
https://eccc.weizmann.ac.il/report/2018/135#revision1We 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 homomorphisms, directed homomorphisms and injective directed homomorphisms and obtain polynomial families complete for VF, VBP, VP, and VNP under each one of these. The polynomial families have the following properties:
* The polynomial families complete for VF, VBP, and VP are model independent, i.e. they do not use a particular instance of a formula, ABP or circuit for characterising VF, VBP, or VP, respectively.
* All the polynomial families are hard under $p$-projections.Wed, 12 Jun 2019 09:05:10 +0300https://eccc.weizmann.ac.il/report/2018/135#revision1
Paper TR18-135
| Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes |
Prasad Chaugule,
Nutan Limaye,
Aditya Varre
https://eccc.weizmann.ac.il/report/2018/135We 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 homomorphisms, directed homomorphisms and injective directed homomorphisms and obtain polynomial families complete for VF, VBP, VP, and VNP under each one of these. The polynomial families have the following properties:
* The polynomial families complete for VF, VBP, and VP are model independent, i.e. they do not use a particular instance of a formula, ABP or circuit for characterising VF, VBP, or VP, respectively.
* All the polynomial families are hard under $p$-projections.Tue, 31 Jul 2018 21:02:42 +0300https://eccc.weizmann.ac.il/report/2018/135