ECCC-Report TR24-021https://eccc.weizmann.ac.il/report/2024/021Comments and Revisions published for TR24-021en-usSun, 04 Feb 2024 09:42:17 +0200
Paper TR24-021
| On the closures of monotone algebraic classes and variants of the determinant |
Prasad Chaugule,
Nutan Limaye
https://eccc.weizmann.ac.il/report/2024/021In this paper we prove the following two results.
* We show that for any $C \in {mVF, mVP, mVNP}$, $C = \overline{C}$. Here, $mVF, mVP$, and $mVNP$ are monotone variants of $VF, VP$, and $VNP$, respectively. For an algebraic complexity class $C$, $\overline{C}$ denotes the closure of $C$. For $mVBP$ a similar result was shown. Here we extend their result by adapting their proof.
* We define polynomial families $\{\mathcal{P}(k)_n\}_{n \geq 0}$, such that $\{\mathcal{P}(0)_n\}_{n \geq 0}$ equals the Determinant polynomial. We show that $\{\mathcal{P}(k)_n\}_{n \geq 0}$ is $VBP$ complete for $k=1$ and becomes $VNP$ complete when $k \geq 2$. In particular, $\{\mathcal{P}(k)_n\}$ is $Det^{\neq k}_n(X)$, a polynomial obtained by summing over all signed cycle covers that avoid length $k$ cycles. We show that $Det^{\neq 1}_n(X)$ is complete for $VBP$ and $Det^{\neq k}_n(X)$ is complete for $VNP$ for all $k \geq 2$ over any field $\mathbb{F}$.
Sun, 04 Feb 2024 09:42:17 +0200https://eccc.weizmann.ac.il/report/2024/021