License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2022.32
URN: urn:nbn:de:0030-drops-165942
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16594/
Limaye, Nutan ;
Srinivasan, Srikanth ;
Tavenas, Sébastien
On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials
Abstract
We make progress on understanding a lower bound technique that was recently used by the authors to prove the first superpolynomial constant-depth circuit lower bounds against algebraic circuits.
More specifically, our previous work applied the well-known partial derivative method in a new setting, that of lopsided set-multilinear polynomials. A set-multilinear 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 set-multilinear 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 partial-derivative method for proving lower bounds, we were able to prove constant-depth superpolynomial set-multilinear formula lower bounds even for very low-degree 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 constant-depth.
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 partial-derivative method used can be modeled as the choice of a multiset W ⊆ [-1,1] of size d. Our first result completely characterizes, for any product-depth Δ, the best lower bound we can prove for set-multilinear formulas of product-depth Δ in terms of some combinatorial properties of W, that we call the depth-Δ tree bias of W.
2) We show that the maximum depth-3 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 set-multilinear formulas of product-depth 3, and also puts a non-trivial 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 product-depth Δ).
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 Set-Multilinear Polynomials}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {32:1--32:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-241-9},
ISSN = {1868-8969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16594},
URN = {urn:nbn:de:0030-drops-165942},
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 |
