Degree-Restricted Strength Decompositions and Algebraic Branching Programs

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

  • Fulltext

    Final published version, 702 KB, PDF document

  • Fulvio Gesmundo
  • Purnata Ghosal
  • Christian Ikenmeyer
  • Vladimir Lysikov

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.

Original languageEnglish
Title of host publication42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022
EditorsAnuj Dawar, Venkatesan Guruswami
Number of pages15
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date2022
Article number20
ISBN (Electronic)9783959772617
DOIs
Publication statusPublished - 2022
Event42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022 - Chennai, India
Duration: 18 Dec 202220 Dec 2022

Conference

Conference42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022
LandIndia
ByChennai
Periode18/12/202220/12/2022
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume250
ISSN1868-8969

Bibliographical note

Publisher Copyright:
© Fulvio Gesmundo, Purnata Ghosal, Christian Ikenmeyer, and Vladimir Lysikov; licensed under Creative Commons License CC-BY 4.0.

    Research areas

  • Algebraic branching programs, Lower bounds, Slice rank, Strength of polynomials

ID: 331252328