Degree-Restricted Strength Decompositions and Algebraic Branching Programs
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Forlagets udgivne version, 702 KB, PDF-dokument
We analyze Kumar's recent quadratic algebraic branching program size lower bound proof method (CCC 2017) for the power sum polynomial. We present a refinement of this method that gives better bounds in some cases. The lower bound relies on Noether-Lefschetz type conditions on the hypersurface defined by the homogeneous polynomial. In the explicit example that we provide, the lower bound is proved resorting to classical intersection theory. Furthermore, we use similar methods to improve the known lower bound methods for slice rank of polynomials. We consider a sequence of polynomials that have been studied before by Shioda and show that for these polynomials the improved lower bound matches the known upper bound.
| Originalsprog | Engelsk |
|---|---|
| Titel | 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022 |
| Redaktører | Anuj Dawar, Venkatesan Guruswami |
| Antal sider | 15 |
| Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Publikationsdato | 2022 |
| Artikelnummer | 20 |
| ISBN (Elektronisk) | 9783959772617 |
| DOI | |
| Status | Udgivet - 2022 |
| Begivenhed | 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022 - Chennai, Indien Varighed: 18 dec. 2022 → 20 dec. 2022 |
Konference
| Konference | 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022 |
|---|---|
| Land | Indien |
| By | Chennai |
| Periode | 18/12/2022 → 20/12/2022 |
| Navn | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Vol/bind | 250 |
| ISSN | 1868-8969 |
Bibliografisk note
Funding Information:
Funding Purnata Ghosal: DFG IK 116/2-1 and EPSRC EP/W014882/1. The work was done while this author was at the University of Liverpool. Christian Ikenmeyer: DFG IK 116/2-1 and EPSRC EP/W014882/1. The work was done while this author was at the University of Liverpool. Vladimir Lysikov: ERC 818761 and VILLUM FONDEN via the QMATH Centre of Excellence (Grant No. 10059).
Funding Information:
Purnata Ghosal: DFG IK 116/2-1 and EPSRC EP/W014882/1. The work was done while this author was at the University of Liverpool. Christian Ikenmeyer: DFG IK 116/2-1 and EPSRC EP/W014882/1. The work was done while this author was at the University of Liverpool. Vladimir Lysikov: ERC 818761 and VILLUM FONDEN via the QMATH Centre of Excellence (Grant No. 10059). We would like to thank Daniele Agostini for many helpful discussions during the development of this work. We also thank Edoardo Ballico, Luca Chiantini, Giorgio Ottaviani and Kristian Ranestad for pointing out useful references on the Noether-Lefschetz property and related results. We thank the anonymous referees for their helpful comments.
Publisher Copyright:
© Fulvio Gesmundo, Purnata Ghosal, Christian Ikenmeyer, and Vladimir Lysikov; licensed under Creative Commons License CC-BY 4.0.
ID: 331252328