2026-08-21T18:34:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27451 2026-08-21T14:42:40Z ddc:004 open_access

On the Tension Between Full-Rankness and Self-Reducibility for Set-Multilinear Polynomials Kush, Deepanshu Algebraic formula lower bounds set-multilinear formulas iterated matrix multiplication rank methods hardness escalation self-reducibility barriers In this paper, we rule out a natural programme for proving VF ≠ VNP via set-multilinear formula lower bounds. The programme combines two ingredients present in the literature: the n^Ω(log n) set-multilinear formula lower bound of Kush and Saraf (CCC 2022) for any full-rank polynomial, and an IMM-style self-reducibility that propagates such a bound to small degree, where Raz’s set-multilinearisation (J. ACM 2013) converts it to a general formula lower bound. Each ingredient has been realised separately, yet no polynomial family is known to combine them. We prove that no such family can exist: under any polynomial-width IMM-style self-reducibility - i.e., a small-width expression g = ∑_{k=1}^w L_k ⋅ R_k with each summand factoring across a balanced split - full-rankness forces width n^Ω(d), and even approximate full-rankness across a near-balanced split forces width n^Ω(√d). This rules out the full-rank/self-reducible route to VF ≠ VNP. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Deepanshu Kush 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.69 urn:nbn:de:0030-drops-274512 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.69 eng https://creativecommons.org/licenses/by/4.0/legalcode