Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Peter Bürgisser, Mahmut Levent Doğan, Visu Makam, Michael Walter, and Avi Wigderson. Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 14:1-14:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{burgisser_et_al:LIPIcs.CCC.2024.14, author = {B\"{u}rgisser, Peter and Do\u{g}an, Mahmut Levent and Makam, Visu and Walter, Michael and Wigderson, Avi}, title = {{Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {14:1--14:48}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.14}, URN = {urn:nbn:de:0030-drops-204100}, doi = {10.4230/LIPIcs.CCC.2024.14}, annote = {Keywords: computational invariant theory, geometric complexity theory, orbit problems, abc-conjecture, closest vector problem} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Maxime Cautrès, Nathan Claudet, Mehdi Mhalla, Simon Perdrix, Valentin Savin, and Stéphan Thomassé. Vertex-Minor Universal Graphs for Generating Entangled Quantum Subsystems. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cautres_et_al:LIPIcs.ICALP.2024.36, author = {Cautr\`{e}s, Maxime and Claudet, Nathan and Mhalla, Mehdi and Perdrix, Simon and Savin, Valentin and Thomass\'{e}, St\'{e}phan}, title = {{Vertex-Minor Universal Graphs for Generating Entangled Quantum Subsystems}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {36:1--36:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.36}, URN = {urn:nbn:de:0030-drops-201796}, doi = {10.4230/LIPIcs.ICALP.2024.36}, annote = {Keywords: Quantum networks, graph states, vertex-minors, k-pairability} }
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 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, and Jeroen Zuiddam. Discreteness of Asymptotic Tensor Ranks (Extended Abstract). In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{briet_et_al:LIPIcs.ITCS.2024.20, author = {Bri\"{e}t, Jop and Christandl, Matthias and Leigh, Itai and Shpilka, Amir and Zuiddam, Jeroen}, title = {{Discreteness of Asymptotic Tensor Ranks}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {20:1--20:14}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.20}, URN = {urn:nbn:de:0030-drops-195483}, doi = {10.4230/LIPIcs.ITCS.2024.20}, annote = {Keywords: Tensors, Asymptotic rank, Subrank, Slice rank, Restriction, Degeneration, Diagonalization, SLOCC} }
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.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 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.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 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Markus Bläser and Vladimir Lysikov. Slice Rank of Block Tensors and Irreversibility of Structure Tensors of Algebras. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{blaser_et_al:LIPIcs.MFCS.2020.17, author = {Bl\"{a}ser, Markus and Lysikov, Vladimir}, title = {{Slice Rank of Block Tensors and Irreversibility of Structure Tensors of Algebras}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {17:1--17:15}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.17}, URN = {urn:nbn:de:0030-drops-126869}, doi = {10.4230/LIPIcs.MFCS.2020.17}, annote = {Keywords: Tensors, Slice rank, Barriers, Matrix multiplication, GIT stability} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Markus Bläser and Vladimir Lysikov. On Degeneration of Tensors and Algebras. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 19:1-19:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{blaser_et_al:LIPIcs.MFCS.2016.19, author = {Bl\"{a}ser, Markus and Lysikov, Vladimir}, title = {{On Degeneration of Tensors and Algebras}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {19:1--19:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.19}, URN = {urn:nbn:de:0030-drops-64343}, doi = {10.4230/LIPIcs.MFCS.2016.19}, annote = {Keywords: bilinear complexity, border rank, commutative algebras, lower bounds} }