Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov. Fixed-Parameter Debordering of Waring Rank. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dutta_et_al:LIPIcs.STACS.2024.30, author = {Dutta, Pranjal and Gesmundo, Fulvio and Ikenmeyer, Christian and Jindal, Gorav and Lysikov, Vladimir}, title = {{Fixed-Parameter Debordering of Waring Rank}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {30:1--30:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.30}, URN = {urn:nbn:de:0030-drops-197403}, doi = {10.4230/LIPIcs.STACS.2024.30}, annote = {Keywords: border complexity, Waring rank, debordering, apolarity} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Pranjal Dutta, Christian Ikenmeyer, Balagopal Komarath, Harshil Mittal, Saraswati Girish Nanoti, and Dhara Thakkar. On the Power of Border Width-2 ABPs over Fields of Characteristic 2. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dutta_et_al:LIPIcs.STACS.2024.31, author = {Dutta, Pranjal and Ikenmeyer, Christian and Komarath, Balagopal and Mittal, Harshil and Nanoti, Saraswati Girish and Thakkar, Dhara}, title = {{On the Power of Border Width-2 ABPs over Fields of Characteristic 2}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {31:1--31:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.31}, URN = {urn:nbn:de:0030-drops-197419}, doi = {10.4230/LIPIcs.STACS.2024.31}, annote = {Keywords: Algebraic branching programs, border complexity, characteristic 2} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov. Homogeneous Algebraic Complexity Theory and Algebraic Formulas. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 43:1-43:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dutta_et_al:LIPIcs.ITCS.2024.43, author = {Dutta, Pranjal and Gesmundo, Fulvio and Ikenmeyer, Christian and Jindal, Gorav and Lysikov, Vladimir}, title = {{Homogeneous Algebraic Complexity Theory and Algebraic Formulas}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {43:1--43:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.43}, URN = {urn:nbn:de:0030-drops-195713}, doi = {10.4230/LIPIcs.ITCS.2024.43}, annote = {Keywords: Homogeneous polynomials, Waring rank, Arithmetic formulas, Border complexity, Geometric Complexity theory, Symmetric polynomials} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Christian Ikenmeyer, Balagopal Komarath, and Nitin Saurabh. Karchmer-Wigderson Games for Hazard-Free Computation. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 74:1-74:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{ikenmeyer_et_al:LIPIcs.ITCS.2023.74, author = {Ikenmeyer, Christian and Komarath, Balagopal and Saurabh, Nitin}, title = {{Karchmer-Wigderson Games for Hazard-Free Computation}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {74:1--74:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.74}, URN = {urn:nbn:de:0030-drops-175775}, doi = {10.4230/LIPIcs.ITCS.2023.74}, annote = {Keywords: Hazard-free computation, monotone computation, Karchmer-Wigderson games, communication complexity, lower bounds} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Fulvio Gesmundo, Purnata Ghosal, Christian Ikenmeyer, and Vladimir Lysikov. Degree-Restricted Strength Decompositions and Algebraic Branching Programs. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{gesmundo_et_al:LIPIcs.FSTTCS.2022.20, author = {Gesmundo, Fulvio and Ghosal, Purnata and Ikenmeyer, Christian and Lysikov, Vladimir}, title = {{Degree-Restricted Strength Decompositions and Algebraic Branching Programs}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {20:1--20:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-261-7}, ISSN = {1868-8969}, year = {2022}, volume = {250}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.20}, URN = {urn:nbn:de:0030-drops-174127}, doi = {10.4230/LIPIcs.FSTTCS.2022.20}, annote = {Keywords: Lower bounds, Slice rank, Strength of polynomials, Algebraic branching programs} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Markus Bläser, Julian Dörfler, and Christian Ikenmeyer. On the Complexity of Evaluating Highest Weight Vectors. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 29:1-29:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{blaser_et_al:LIPIcs.CCC.2021.29, author = {Bl\"{a}ser, Markus and D\"{o}rfler, Julian and Ikenmeyer, Christian}, title = {{On the Complexity of Evaluating Highest Weight Vectors}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {29:1--29:36}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.29}, URN = {urn:nbn:de:0030-drops-143036}, doi = {10.4230/LIPIcs.CCC.2021.29}, annote = {Keywords: Algebraic complexity theory, geometric complexity theory, algebraic branching program, Waring rank, border Waring rank, representation theory, highest weight vector, treewidth} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Janaky Murthy, Vineet Nair, and Chandan Saha. Randomized Polynomial-Time Equivalence Between Determinant and Trace-IMM Equivalence Tests. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 72:1-72:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{murthy_et_al:LIPIcs.MFCS.2020.72, author = {Murthy, Janaky and Nair, Vineet and Saha, Chandan}, title = {{Randomized Polynomial-Time Equivalence Between Determinant and Trace-IMM Equivalence Tests}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {72:1--72:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.72}, URN = {urn:nbn:de:0030-drops-127419}, doi = {10.4230/LIPIcs.MFCS.2020.72}, annote = {Keywords: equivalence testing, determinant, trace of the matrix product, full-matrix algebra isomorphism} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Ankit Garg, Christian Ikenmeyer, Visu Makam, Rafael Oliveira, Michael Walter, and Avi Wigderson. Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{garg_et_al:LIPIcs.CCC.2020.12, author = {Garg, Ankit and Ikenmeyer, Christian and Makam, Visu and Oliveira, Rafael and Walter, Michael and Wigderson, Avi}, title = {{Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {12:1--12:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.12}, URN = {urn:nbn:de:0030-drops-125645}, doi = {10.4230/LIPIcs.CCC.2020.12}, annote = {Keywords: generators for invariant rings, succinct encodings} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, and Nitin Saurabh. Algebraic Branching Programs, Border Complexity, and Tangent Spaces. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{blaser_et_al:LIPIcs.CCC.2020.21, author = {Bl\"{a}ser, Markus and Ikenmeyer, Christian and Mahajan, Meena and Pandey, Anurag and Saurabh, Nitin}, title = {{Algebraic Branching Programs, Border Complexity, and Tangent Spaces}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {21:1--21:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.21}, URN = {urn:nbn:de:0030-drops-125733}, doi = {10.4230/LIPIcs.CCC.2020.21}, annote = {Keywords: Algebraic Branching Programs, Border Complexity, Tangent Spaces, Lower Bounds, Geometric Complexity Theory, Flows, VQP, VNP} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Cornelius Brand. Patching Colors with Tensors. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{brand:LIPIcs.ESA.2019.25, author = {Brand, Cornelius}, title = {{Patching Colors with Tensors}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {25:1--25:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.25}, URN = {urn:nbn:de:0030-drops-111467}, doi = {10.4230/LIPIcs.ESA.2019.25}, annote = {Keywords: Color-Coding, Extensor-Coding, internal out-branching, colorful problems, algebraic algorithms, multilinear detection, deterministic algorithms, exterior algebra} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Julian Dörfler, Christian Ikenmeyer, and Greta Panova. On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dorfler_et_al:LIPIcs.ICALP.2019.51, author = {D\"{o}rfler, Julian and Ikenmeyer, Christian and Panova, Greta}, title = {{On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {51:1--51:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.51}, URN = {urn:nbn:de:0030-drops-106276}, doi = {10.4230/LIPIcs.ICALP.2019.51}, annote = {Keywords: Algebraic complexity theory, geometric complexity theory, Waring rank, plethysm coefficients, occurrence obstructions, multiplicity obstructions} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Karl Bringmann, Christian Ikenmeyer, and Jeroen Zuiddam. On Algebraic Branching Programs of Small Width. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 20:1-20:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bringmann_et_al:LIPIcs.CCC.2017.20, author = {Bringmann, Karl and Ikenmeyer, Christian and Zuiddam, Jeroen}, title = {{On Algebraic Branching Programs of Small Width}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {20:1--20:31}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.20}, URN = {urn:nbn:de:0030-drops-75217}, doi = {10.4230/LIPIcs.CCC.2017.20}, annote = {Keywords: algebraic branching programs, algebraic complexity theory, border complexity, formula size, iterated matrix multiplication} }
Feedback for Dagstuhl Publishing