2026-07-20T05:27:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22878 2025-10-02T13:36:16Z ddc:004 open_access

On Read-k Projections of the Determinant Hrubeš, Pavel Joglekar, Pushkar S. determinant permanent projection of determinant VNP completeness of permanent 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 read-k, if every variable occurs at most k times in M. It will be called a determinantal representation of a polynomial f if f = det(M). We show that - the n × n permanent polynomial does not have a read-k determinantal representation for k ∈ o(√n/log n) (over a field of characteristic different from two). We also obtain a quantitative strengthening of this result by giving a similar non-expressibility for k ∈ o(√n/log n) for an explicit n-variate multilinear polynomial (as opposed to the permanent which is n²-variate). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pavel Hrubeš and Pushkar S. Joglekar 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.53 urn:nbn:de:0030-drops-228785 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.53 eng https://creativecommons.org/licenses/by/4.0/legalcode