2026-07-23T07:56:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9040 2024-03-06T10:43:13Z ddc:004 open_access

A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas Chillara, Suryajith Limaye, Nutan Srinivasan, Srikanth Algebraic circuit complexity Multilinear formulas Lower Bounds We show explicit separations between the expressive powers of multilinear formulas of small-depth and all polynomial sizes. Formally, for any s = s(n) = n^{O(1)} and any delta>0, we construct explicit families of multilinear polynomials P_n in F[x_1,...,x_n] that have multilinear formulas of size s and depth three but no multilinear formulas of size s^{1/2-delta} and depth o(log n/log log n). As far as we know, this is the first such result for an algebraic model of computation. Our proof can be viewed as a derandomization of a lower bound technique of Raz (JACM 2009) using epsilon-biased spaces. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Suryajith Chillara and Nutan Limaye and Srikanth Srinivasan 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.36 urn:nbn:de:0030-drops-90401 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.36 eng https://creativecommons.org/licenses/by/3.0/legalcode