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.2023.15
URN: urn:nbn:de:0030-drops-182855
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18285/
Kush, Deepanshu ;
Saraf, Shubhangi
Near-Optimal Set-Multilinear Formula Lower Bounds
Abstract
The seminal work of Raz (J. ACM 2013) as well as the recent breakthrough results by Limaye, Srinivasan, and Tavenas (FOCS 2021, STOC 2022) have demonstrated a potential avenue for obtaining lower bounds for general algebraic formulas, via strong enough lower bounds for set-multilinear formulas.
In this paper, we make progress along this direction by proving near-optimal lower bounds against low-depth as well as unbounded-depth set-multilinear formulas. More precisely, we show that over any field of characteristic zero, there is a polynomial f computed by a polynomial-sized set-multilinear branching program (i.e., f is in set-multilinear VBP) 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/Δ}/Δ). Moreover, we show that any unbounded-depth set-multilinear formula computing f has size at least n^{Ω(log n)}.
If such strong lower bounds are proven for the iterated matrix multiplication (IMM) polynomial or rather, any polynomial that is computed by an ordered set-multilinear branching program (i.e., a further restriction of set-multilinear VBP), then this would have dramatic consequences as it would imply super-polynomial lower bounds for general algebraic formulas (Raz, J. ACM 2013; Tavenas, Limaye, and Srinivasan, STOC 2022).
Prior to our work, either only weaker lower bounds were known for the IMM polynomial (Tavenas, Limaye, and Srinivasan, STOC 2022), or similar strong lower bounds were known but for a hard polynomial not known to be even in set-multilinear VP (Kush and Saraf, CCC 2022; Raz, J. ACM 2009).
By known depth-reduction results, our lower bounds are essentially tight for f and in general, for any hard polynomial that is in set-multilinear VBP or set-multilinear VP. Any asymptotic improvement in the lower bound (for a hard polynomial, say, in VNP) would imply super-polynomial lower bounds for general set-multilinear circuits.
BibTeX - Entry
@InProceedings{kush_et_al:LIPIcs.CCC.2023.15,
author = {Kush, Deepanshu and Saraf, Shubhangi},
title = {{Near-Optimal Set-Multilinear Formula Lower Bounds}},
booktitle = {38th Computational Complexity Conference (CCC 2023)},
pages = {15:1--15:33},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-282-2},
ISSN = {1868-8969},
year = {2023},
volume = {264},
editor = {Ta-Shma, Amnon},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18285},
URN = {urn:nbn:de:0030-drops-182855},
doi = {10.4230/LIPIcs.CCC.2023.15},
annote = {Keywords: Algebraic Complexity, Set-multilinear, Formula Lower Bounds}
}
|
Keywords: |
|
Algebraic Complexity, Set-multilinear, Formula Lower Bounds |
|
Collection: |
|
38th Computational Complexity Conference (CCC 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
10.07.2023 |
