Name
Abstract | ||
|---|---|---|
We prove new barrier results in arithmetic complexity theory, showing severe limitations of natural lifting (aka escalation) techniques. For example, we prove that even optimal rank lower bounds on k-tensors cannot yield non-trivial lower bounds on the rank of d-tensors, for any constant d larger than k. This significantly extends recent barrier results on the limits of (matrix) rank methods by [EGOW17], which handles the (very important) case k=2. Our generalization requires the development of new technical tools and results in algebraic geometry, which are interesting in their own right and possibly applicable elsewhere. The basic issue they probe is the relation between numeric and symbolic rank of tensors, essential in the proofs of previous and current barriers. Our main technical result implies that for every symbolic k-tensor (namely one whose entries are polynomials in some set of variables), if the tensor rank is small for every evaluation of the variables, then it is small symbolically. This statement is obvious for k=2. To prove an analogous statement for k larger than 2 we develop a "numeric to symbolic'' transfer of algebraic %analytic relations to algebraic %analytic functions, somewhat in the spirit of the implicit function theorem. It applies in the general setting of inclusion of images of polynomial maps, in the form appearing in Raz's elusive functions approach to proving VP ≠ VNP. We give a toy application showing how our transfer theorem may be useful in pursuing this approach to prove arithmetic complexity lower bounds. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1109/FOCS.2019.00054 | 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | Field | DocType |
tensor rank,waring rank,rank methods,lifting,barriers | Discrete mathematics,Algebraic geometry,Tensor,Polynomial,Implicit function theorem,Matrix (mathematics),Algebraic function,Mathematical proof,AKA,Mathematics | Journal |
Volume | ISSN | ISBN |
abs/1904.04299 | 1523-8288 | 978-1-7281-4953-0 |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ankit Garg | 1 | 125 | 16.19 |
| Visu Makam | 2 | 0 | 1.35 |
| Rafael Mendes de Oliveira | 3 | 49 | 7.59 |
| Avi Wigderson | 4 | 8205 | 1064.31 |