License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2018.1
URN: urn:nbn:de:0030-drops-83506
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8350/
Efremenko, Klim ;
Garg, Ankit ;
Oliveira, Rafael ;
Wigderson, Avi
Barriers for Rank Methods in Arithmetic Complexity
Abstract
Arithmetic complexity, the study of the cost of computing polynomials via additions and multiplications, is considered (for many good reasons) simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than in Boolean complexity. Despite many successes and rapid progress, however, foundational challenges, like proving super-polynomial lower bounds on circuit or formula size for explicit polynomials, or super-linear lower bounds on explicit 3-dimensional tensors, remain elusive.
At the same time (and possibly for similar reasons), we have plenty more excuses, in the form of "barrier results" for failing to prove basic lower bounds in Boolean complexity than in arithmetic complexity. Efforts to find barriers to arithmetic lower bound techniques seem harder, and despite some attempts we have no excuses of similar quality for these failures in arithmetic complexity. This paper aims to add to this study.
In this paper we address rank methods, which were long recognized as encompassing and abstracting almost all known arithmetic lower bounds to-date, including the most recent impressive successes. Rank methods (under the name of flattenings) are also in wide use in algebraic geometry for proving tensor rank and symmetric tensor rank lower bounds. Our main results are barriers to these methods. In particular,
1. Rank methods cannot prove better than (2^d)*n^(d/2) lower bound on the tensor rank of any d-dimensional tensor of side n. (In particular, they cannot prove super-linear, indeed even >8n tensor rank lower bounds for any 3-dimensional tensors.)
2. Rank methods cannot prove (d+1)n^(d/2) on the Waring rank of any n-variate polynomial of degree d. (In particular, they cannot prove such lower bounds on stronger models, including depth-3 circuits.)
The proofs of these bounds use simple linear-algebraic arguments, leveraging connections between the symbolic rank of matrix polynomials and the usual rank of their evaluations. These techniques can perhaps be extended to barriers for other arithmetic models on which progress has halted.
To see how these barrier results directly inform the state-of-art in arithmetic complexity we note the following.
First, the bounds above nearly match the best explicit bounds we know for these models, hence offer an explanations why the rank methods got stuck there. Second, the bounds above are a far cry (quadratically away) from the true complexity (e.g. of random polynomials) in these models, which if achieved (by any methods), are known to imply super-polynomial formula lower bounds.
We also explain the relation of our barrier results to other attempts, and in particular how they significantly differ from the recent attempts to find analogues of "natural proofs" for arithmetic complexity. Finally, we discuss the few arithmetic lower bound approaches which fall outside rank methods, and some natural directions our barriers suggest.
BibTeX - Entry
@InProceedings{efremenko_et_al:LIPIcs:2018:8350,
author = {Klim Efremenko and Ankit Garg and Rafael Oliveira and Avi Wigderson},
title = {{Barriers for Rank Methods in Arithmetic Complexity}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {1:1--1:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8350},
URN = {urn:nbn:de:0030-drops-83506},
doi = {10.4230/LIPIcs.ITCS.2018.1},
annote = {Keywords: Lower Bounds, Barriers, Partial Derivatives, Flattenings, Algebraic Complexity}
}
|
Keywords: |
|
Lower Bounds, Barriers, Partial Derivatives, Flattenings, Algebraic Complexity |
|
Collection: |
|
9th Innovations in Theoretical Computer Science Conference (ITCS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
12.01.2018 |
