Standard
Degree-Restricted Strength Decompositions and Algebraic Branching Programs. / Gesmundo, Fulvio; Ghosal, Purnata; Ikenmeyer, Christian; Lysikov, Vladimir.
42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022. red. / Anuj Dawar; Venkatesan Guruswami. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. 20 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 250).
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
Gesmundo, F, Ghosal, P, Ikenmeyer, C & Lysikov, V 2022,
Degree-Restricted Strength Decompositions and Algebraic Branching Programs. i A Dawar & V Guruswami (red),
42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022., 20, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, bind 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022, Chennai, Indien,
18/12/2022.
https://doi.org/10.4230/LIPIcs.FSTTCS.2022.20APA
Gesmundo, F., Ghosal, P., Ikenmeyer, C., & Lysikov, V. (2022).
Degree-Restricted Strength Decompositions and Algebraic Branching Programs. I A. Dawar, & V. Guruswami (red.),
42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022 [20] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Bind 250
https://doi.org/10.4230/LIPIcs.FSTTCS.2022.20Vancouver
Gesmundo F, Ghosal P, Ikenmeyer C, Lysikov V.
Degree-Restricted Strength Decompositions and Algebraic Branching Programs. I Dawar A, Guruswami V, red., 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2022. 20. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 250).
https://doi.org/10.4230/LIPIcs.FSTTCS.2022.20Author
Gesmundo, Fulvio ; Ghosal, Purnata ; Ikenmeyer, Christian ; Lysikov, Vladimir. / Degree-Restricted Strength Decompositions and Algebraic Branching Programs. 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022. red. / Anuj Dawar ; Venkatesan Guruswami. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 250).
Bibtex
@inproceedings{62137c02b3bf4fe8a7751a95babdece8,
title = "Degree-Restricted Strength Decompositions and Algebraic Branching Programs",
abstract = "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.",
keywords = "Algebraic branching programs, Lower bounds, Slice rank, Strength of polynomials",
author = "Fulvio Gesmundo and Purnata Ghosal and Christian Ikenmeyer and Vladimir Lysikov",
note = "Publisher Copyright: {\textcopyright} Fulvio Gesmundo, Purnata Ghosal, Christian Ikenmeyer, and Vladimir Lysikov; licensed under Creative Commons License CC-BY 4.0.; 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022 ; Conference date: 18-12-2022 Through 20-12-2022",
year = "2022",
doi = "10.4230/LIPIcs.FSTTCS.2022.20",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Anuj Dawar and Venkatesan Guruswami",
booktitle = "42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022",
}
RIS
TY - GEN
T1 - Degree-Restricted Strength Decompositions and Algebraic Branching Programs
AU - Gesmundo, Fulvio
AU - Ghosal, Purnata
AU - Ikenmeyer, Christian
AU - Lysikov, Vladimir
N1 - Publisher Copyright:
© Fulvio Gesmundo, Purnata Ghosal, Christian Ikenmeyer, and Vladimir Lysikov; licensed under Creative Commons License CC-BY 4.0.
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
KW - Algebraic branching programs
KW - Lower bounds
KW - Slice rank
KW - Strength of polynomials
UR - http://www.scopus.com/inward/record.url?scp=85144334582&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.FSTTCS.2022.20
DO - 10.4230/LIPIcs.FSTTCS.2022.20
M3 - Article in proceedings
AN - SCOPUS:85144334582
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022
A2 - Dawar, Anuj
A2 - Guruswami, Venkatesan
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022
Y2 - 18 December 2022 through 20 December 2022
ER -
