Abstract
We make progress on understanding a lower bound technique that was recently used by the authors to prove the first superpolynomial constantdepth circuit lower bounds against algebraic circuits.
More specifically, our previous work applied the wellknown partial derivative method in a new setting, that of lopsided setmultilinear polynomials. A setmultilinear polynomial P ∈ ?[X_1,…,X_d] (for disjoint sets of variables X_1,…,X_d) is a linear combination of monomials, each of which contains one variable from X_1,…,X_d. A lopsided space of setmultilinear polynomials is one where the sets X_1,…,X_d are allowed to have different sizes (we use the adjective "lopsided" to stress this feature). By choosing a suitable lopsided space of polynomials, and using a suitable version of the partialderivative method for proving lower bounds, we were able to prove constantdepth superpolynomial setmultilinear formula lower bounds even for very lowdegree polynomials (as long as d is a growing function of the number of variables N). This in turn implied lower bounds against general formulas of constantdepth.
A priori, there is nothing stopping these techniques from giving us lower bounds against algebraic formulas of any depth. We investigate the extent to which this lower bound can extend to greater depths. We prove the following results.
1) We observe that our choice of the lopsided space and the kind of partialderivative method used can be modeled as the choice of a multiset W ⊆ [1,1] of size d. Our first result completely characterizes, for any productdepth Δ, the best lower bound we can prove for setmultilinear formulas of productdepth Δ in terms of some combinatorial properties of W, that we call the depthΔ tree bias of W.
2) We show that the maximum depth3 tree bias, over multisets W of size d, is Θ(d^{1/4}). This shows a stronger formula lower bound of N^{Ω(d^{1/4})} for setmultilinear formulas of productdepth 3, and also puts a nontrivial constraint on the best lower bounds we can hope to prove at this depth in this framework (a priori, we could have hoped to prove a lower bound of N^{Ω(Δ d^{1/Δ})} at productdepth Δ).
3) Finally, we show that for small Δ, our proof technique cannot hope to prove lower bounds of the form N^{Ω(d^{1/poly(Δ)})}. This seems to strongly hint that new ideas will be required to prove lower bounds for formulas of unbounded depth.
BibTeX  Entry
@InProceedings{limaye_et_al:LIPIcs.CCC.2022.32,
author = {Limaye, Nutan and Srinivasan, Srikanth and Tavenas, S\'{e}bastien},
title = {{On the Partial Derivative Method Applied to Lopsided SetMultilinear Polynomials}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {32:132:23},
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/16594},
URN = {urn:nbn:de:0030drops165942},
doi = {10.4230/LIPIcs.CCC.2022.32},
annote = {Keywords: Partial Derivative Method, Barriers to Lower Bounds}
}
Keywords: 

Partial Derivative Method, Barriers to Lower Bounds 
Collection: 

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

2022 
Date of publication: 

11.07.2022 