The Library
Fixed-parameter debordering of Waring rank
Tools
Dutta, Pranjal, Gesmundo, Fulvio, Ikenmeyer, Christian, Jindal, Gorav and Lysikov, Vladimir (2024) Fixed-parameter debordering of Waring rank. In: 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), Clermont-Ferrand, France, 12-14 Mar 2024. Published in: Leibniz International Proceedings in Informatics (LIPIcs) ISSN 1868-8969. (In Press)
|
PDF
WRAP-fixed-parameter-debordering-Waring-rank-2024.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (921Kb) | Preview |
Abstract
Border complexity measures are defined via limits (or topological closures), so that any function which can approximated arbitrarily closely by low complexity functions itself has low border complexity. Debordering is the task of proving an upper bound on some non-border complexity measure in terms of a border complexity measure, thus getting rid of limits.
Debordering is at the heart of understanding the difference between Valiant's determinant vs permanent conjecture, and Mulmuley and Sohoni's variation which uses border determinantal complexity. The debordering of matrix multiplication tensors by Bini played a pivotal role in the development of efficient matrix multiplication algorithms. Consequently, debordering finds applications in both establishing computational complexity lower bounds and facilitating algorithm design. Currently, very few debordering results are known.
In this work, we study the question of debordering the border Waring rank of polynomials. Waring and border Waring rank are very well studied measures in the context of invariant theory, algebraic geometry, and matrix multiplication algorithms. For the first time, we obtain a Waring rank upper bound that is exponential in the border Waring rank and only linear in the degree. All previous known results were exponential in the degree. For polynomials with constant border Waring rank, our results imply an upper bound on the Waring rank linear in degree, which previously was only known for polynomials with border Waring rank at most 5.
Item Type: | Conference Item (Paper) | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > Q Science (General) Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||||||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||||||||||||||
Library of Congress Subject Headings (LCSH): | Machine theory, Information theory, Computer science -- Mathematics, Geometry, Algebraic, Computational complexity, Polynomials | ||||||||||||||||||||||||
Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||||||||||||||||||||
Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | ||||||||||||||||||||||||
ISSN: | 1868-8969 | ||||||||||||||||||||||||
Official Date: | 2024 | ||||||||||||||||||||||||
Dates: |
|
||||||||||||||||||||||||
Status: | Peer Reviewed | ||||||||||||||||||||||||
Publication Status: | In Press | ||||||||||||||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||||||||||||||
Date of first compliant deposit: | 20 February 2024 | ||||||||||||||||||||||||
Date of first compliant Open Access: | 21 February 2024 | ||||||||||||||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||||||||||||||
Conference Paper Type: | Paper | ||||||||||||||||||||||||
Title of Event: | 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) | ||||||||||||||||||||||||
Type of Event: | Conference | ||||||||||||||||||||||||
Location of Event: | Clermont-Ferrand, France | ||||||||||||||||||||||||
Date(s) of Event: | 12-14 Mar 2024 | ||||||||||||||||||||||||
Related URLs: | |||||||||||||||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year