Published by the Department of Computer Science, The University of Chicago.
Nutan Limaye
IT University of Copenhagen
Copenhagen, Denmark
nuli AT itu DOT dk
and
Shourya Pandey
University of Texas at Austin
Austin, TX, USA
shouryap AT utexas DOT edu
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 ${\tt StackDet}_n(X)$ and ${\tt 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 combinatorial characterisation of the determinant developed by Mahajan and Vinay (SODA 1997). We extend the combinatorial object in their work, namely $\textit{clow sequences}$, by introducing additional edge labels on the edges of the underlying graph. The idea of using edge labels is inspired by the work of Mengel (MFCS 2013).
Submitted March 20, 2024, revised April 12, 2026, published July 24, 2026.
Licensed under a Creative Commons Attribution License ![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/up.gif)
Volume 2025, Article 1
![[back]](http://www.cs.uchicago.edu/publications/cjtcs/art/back.gif)
Volume 2025
Published articles
![[CJTCS home]](http://www.cs.uchicago.edu/publications/cjtcs/art/logo_www_button.gif){kind=logo}