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.38
URN: urn:nbn:de:0030-drops-166003
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16600/
Kush, Deepanshu ;
Saraf, Shubhangi
Improved Low-Depth Set-Multilinear Circuit Lower Bounds
Abstract
In this paper, we prove strengthened lower bounds for constant-depth set-multilinear 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 product-depth Δ set-multilinear formula computing f has size at least n^Ω(n^{1/Δ}/Δ). The hard polynomial f comes from the class of Nisan-Wigderson (NW) design-based 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 product-depth Δ set-multilinear 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 set-multilinear circuit lower bounds via depth reduction results.
In the setting of general set-multilinear 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 set-multilinear formula lower bounds, and allow them to obtain a lower bound of the form (log n)^Ω(log n) for the size of general set-multilinear 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 unbounded-depth set-multilinear formulas could be obtained for the IMM polynomial, then using the self-reducibility of IMM and using hardness escalation results, this would imply super-polynomial lower bounds for general algebraic formulas.
BibTeX - Entry
@InProceedings{kush_et_al:LIPIcs.CCC.2022.38,
author = {Kush, Deepanshu and Saraf, Shubhangi},
title = {{Improved Low-Depth Set-Multilinear Circuit Lower Bounds}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {38:1--38:16},
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/16600},
URN = {urn:nbn:de:0030-drops-166003},
doi = {10.4230/LIPIcs.CCC.2022.38},
annote = {Keywords: algebraic circuit complexity, complexity measure, set-multilinear formulas}
}
|
Keywords: |
|
algebraic circuit complexity, complexity measure, set-multilinear formulas |
|
Collection: |
|
37th Computational Complexity Conference (CCC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
11.07.2022 |
