Loading jsMath...
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: 297
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