Abstract
In this paper, we prove strengthened lower bounds for constantdepth setmultilinear formulas. More precisely, we show that over any field, there is an explicit polynomial f in VNP defined over n² variables, and of degree n, such that any productdepth Δ setmultilinear formula computing f has size at least n^Ω(n^{1/Δ}/Δ). The hard polynomial f comes from the class of NisanWigderson (NW) designbased polynomials.
Our lower bounds improve upon the recent work of Limaye, Srinivasan and Tavenas (STOC 2022), where a lower bound of the form (log n)^Ω(Δ n^{1/Δ}) was shown for the size of productdepth Δ setmultilinear formulas computing the iterated matrix multiplication (IMM) polynomial of the same degree and over the same number of variables as f. Moreover, our lower bounds are novel for any Δ ≥ 2.
The precise quantitative expression in our lower bound is interesting also because the lower bounds we obtain are "sharp" in the sense that any asymptotic improvement would imply general setmultilinear circuit lower bounds via depth reduction results.
In the setting of general setmultilinear formulas, a lower bound of the form n^Ω(log n) was already obtained by Raz (J. ACM 2009) for the more general model of multilinear formulas. The techniques of LST (which extend the techniques of the same authors in (FOCS 2021)) give a different route to setmultilinear formula lower bounds, and allow them to obtain a lower bound of the form (log n)^Ω(log n) for the size of general setmultilinear formulas computing the IMM polynomial. Our proof techniques are another variation on those of LST, and enable us to show an improved lower bound (matching that of Raz) of the form n^Ω(log n), albeit for the same polynomial f in VNP (the NW polynomial). As observed by LST, if the same n^Ω(log n) size lower bounds for unboundeddepth setmultilinear formulas could be obtained for the IMM polynomial, then using the selfreducibility of IMM and using hardness escalation results, this would imply superpolynomial lower bounds for general algebraic formulas.
BibTeX  Entry
@InProceedings{kush_et_al:LIPIcs.CCC.2022.38,
author = {Kush, Deepanshu and Saraf, Shubhangi},
title = {{Improved LowDepth SetMultilinear Circuit Lower Bounds}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {38:138:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772419},
ISSN = {18688969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16600},
URN = {urn:nbn:de:0030drops166003},
doi = {10.4230/LIPIcs.CCC.2022.38},
annote = {Keywords: algebraic circuit complexity, complexity measure, setmultilinear formulas}
}
Keywords: 

algebraic circuit complexity, complexity measure, setmultilinear formulas 
Collection: 

37th Computational Complexity Conference (CCC 2022) 
Issue Date: 

2022 
Date of publication: 

11.07.2022 