ECCC-Report TR24-125https://eccc.weizmann.ac.il/report/2024/125Comments and Revisions published for TR24-125en-usSun, 28 Jul 2024 12:36:42 +0300
Paper TR24-125
| On read-$k$ projections of the determinant |
Pavel Hrubes,
Pushkar Joglekar
https://eccc.weizmann.ac.il/report/2024/125We consider read-$k$ determinantal representations of polynomials and prove some non-expressibility results. A square matrix $M$ whose entries are variables or field elements will be called \emph{read-$k$}, if every variable occurs at most $k$ times in $M$. It will be called a \emph{determinantal representation} of a polynomial $f$ if $f=\det(M)$. We show that
\begin{itemize}
\item the $n \times n$ permanent polynomial does not have a read-$k$ determinantal representation for $k \in o({\sqrt{n}}/\log n)$ (over a field of characteristic different from two).
\end{itemize}
We also obtain a quantitative strengthening of this result by giving a similar non-expressibility for $k\in o(\sqrt{n}/\log n)$ for an explicit \emph{$n$-variate} multilinear polynomial (as opposed to the permanent which is $n^2$-variate).
Sun, 28 Jul 2024 12:36:42 +0300https://eccc.weizmann.ac.il/report/2024/125