2026-07-21T23:19:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5054 2024-03-06T10:35:47Z ddc:004 open_access

Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas Oliveira, Rafael Shpilka, Amir Volk, Ben Lee Arithmetic Circuits Derandomization Polynomial Identity Testing In this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain lower bounds for these models. For depth-3 multilinear formulas, of size exp(n^delta), we give a hitting set of size exp(~O(n^(2/3 + 2*delta/3))). This implies a lower bound of exp(~Omega(n^(1/2))) for depth-3 multilinear formulas, for some explicit polynomial. For depth-4 multilinear formulas, of size exp(n^delta), we give a hitting set of size exp(~O(n^(2/3 + 4*delta/3)). This implies a lower bound of exp(~Omega(n^(1/4))) for depth-4 multilinear formulas, for some explicit polynomial. A regular formula consists of alternating layers of +,* gates, where all gates at layer i have the same fan-in. We give a hitting set of size (roughly) exp(n^(1-delta)), for regular depth-d multilinear formulas of size exp(n^delta), where delta = O(1/sqrt(5)^d)). This result implies a lower bound of roughly exp(~Omega(n^(1/sqrt(5)^d))) for such formulas. We note that better lower bounds are known for these models, but also that none of these bounds was achieved via construction of a hitting set. Moreover, no lower bound that implies such PIT results, even in the white-box model, is currently known. Our results are combinatorial in nature and rely on reducing the underlying formula, first to a depth-4 formula, and then to a read-once algebraic branching program (from depth-3 formulas we go straight to read-once algebraic branching programs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rafael Oliveira and Amir Shpilka and Ben Lee Volk 2015 Is Part Of LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2015.304 urn:nbn:de:0030-drops-50548 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.304 eng https://creativecommons.org/licenses/by/3.0/legalcode