Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-125 | 19th July 2024 10:56

On read-$k$ projections of the determinant

RSS-Feed




TR24-125
Authors: Pavel Hrubes, Pushkar Joglekar
Publication: 28th July 2024 12:36
Downloads: 220
Keywords: 


Abstract:

We 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).



ISSN 1433-8092 | Imprint