Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with VP-completeness:
TR20-152 | 7th October 2020
Prasad Chaugule, Nutan Limaye, Shourya Pandey

Variants of the Determinant polynomial and VP-completeness

The determinant is a canonical VBP-complete polynomial in the algebraic complexity setting. In this work, we introduce two variants of the determinant polynomial which we call $StackDet_n(X)$ and $CountDet_n(X)$ and show that they are VP and VNP complete respectively under $p$-projections. The definitions of the polynomials are inspired by a ... more >>>

ISSN 1433-8092 | Imprint