Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > VNP COMPLETENESS OF PERMANENT:
Reports tagged with VNP completeness of permanent:
TR24-125 | 19th July 2024
Pavel Hrubes, Pushkar Joglekar

On read-$k$ projections of the determinant

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)$. ... more >>>




ISSN 1433-8092 | Imprint