Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Carla Groenland, Isja Mannens, Jesper Nederlof, Marta Piecyk, and Paweł Rzążewski. Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 77:1-77:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{groenland_et_al:LIPIcs.ICALP.2024.77, author = {Groenland, Carla and Mannens, Isja and Nederlof, Jesper and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {77:1--77:21}, 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.77}, URN = {urn:nbn:de:0030-drops-202208}, doi = {10.4230/LIPIcs.ICALP.2024.77}, annote = {Keywords: graph homomorphism, cutwidth, asymptotic matrix parameters} }
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 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Markus Bläser, Hendrik Mayer, and Devansh Shringi. On the Multilinear Complexity of Associative Algebras. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{blaser_et_al:LIPIcs.STACS.2023.12, author = {Bl\"{a}ser, Markus and Mayer, Hendrik and Shringi, Devansh}, title = {{On the Multilinear Complexity of Associative Algebras}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {12:1--12:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.12}, URN = {urn:nbn:de:0030-drops-176645}, doi = {10.4230/LIPIcs.STACS.2023.12}, annote = {Keywords: Multilinear computations, associative algebras, matrix multiplication, Alder-Strassen theorem} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
James Cook and Ian Mertz. Trading Time and Space in Catalytic Branching Programs. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{cook_et_al:LIPIcs.CCC.2022.8, author = {Cook, James and Mertz, Ian}, title = {{Trading Time and Space in Catalytic Branching Programs}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {8:1--8:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.8}, URN = {urn:nbn:de:0030-drops-165708}, doi = {10.4230/LIPIcs.CCC.2022.8}, annote = {Keywords: complexity theory, branching programs, amortized, space complexity, catalytic computation} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Harm Derksen, Visu Makam, and Jeroen Zuiddam. Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{derksen_et_al:LIPIcs.CCC.2022.9, author = {Derksen, Harm and Makam, Visu and Zuiddam, Jeroen}, title = {{Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {9:1--9:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.9}, URN = {urn:nbn:de:0030-drops-165716}, doi = {10.4230/LIPIcs.CCC.2022.9}, annote = {Keywords: tensors, bilinear maps, complexity, subrank, diagonalization, generic tensors, random tensors, reduction, slice rank} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Matthias Christandl, Omar Fawzi, Hoang Ta, and Jeroen Zuiddam. Larger Corner-Free Sets from Combinatorial Degenerations. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 48:1-48:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{christandl_et_al:LIPIcs.ITCS.2022.48, author = {Christandl, Matthias and Fawzi, Omar and Ta, Hoang and Zuiddam, Jeroen}, title = {{Larger Corner-Free Sets from Combinatorial Degenerations}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {48:1--48:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.48}, URN = {urn:nbn:de:0030-drops-156441}, doi = {10.4230/LIPIcs.ITCS.2022.48}, annote = {Keywords: Corner-free sets, communication complexity, number on the forehead, combinatorial degeneration, hypergraphs, Shannon capacity, eval problem} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam. Geometric Rank of Tensors and Subrank of Matrix Multiplication. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 35:1-35:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kopparty_et_al:LIPIcs.CCC.2020.35, author = {Kopparty, Swastik and Moshkovitz, Guy and Zuiddam, Jeroen}, title = {{Geometric Rank of Tensors and Subrank of Matrix Multiplication}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {35:1--35:21}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.35}, URN = {urn:nbn:de:0030-drops-125874}, doi = {10.4230/LIPIcs.CCC.2020.35}, annote = {Keywords: Algebraic complexity theory, Extremal combinatorics, Tensors, Bias, Analytic rank, Algebraic geometry, Matrix multiplication} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Josh Alman. Limits on the Universal Method for Matrix Multiplication. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 12:1-12:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{alman:LIPIcs.CCC.2019.12, author = {Alman, Josh}, title = {{Limits on the Universal Method for Matrix Multiplication}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {12:1--12:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.12}, URN = {urn:nbn:de:0030-drops-108347}, doi = {10.4230/LIPIcs.CCC.2019.12}, annote = {Keywords: Matrix Multiplication, Laser Method, Slice Rank} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Matthias Christandl, Péter Vrana, and Jeroen Zuiddam. Barriers for Fast Matrix Multiplication from Irreversibility. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{christandl_et_al:LIPIcs.CCC.2019.26, author = {Christandl, Matthias and Vrana, P\'{e}ter and Zuiddam, Jeroen}, title = {{Barriers for Fast Matrix Multiplication from Irreversibility}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {26:1--26:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.26}, URN = {urn:nbn:de:0030-drops-108487}, doi = {10.4230/LIPIcs.CCC.2019.26}, annote = {Keywords: Matrix multiplication exponent, barriers, laser method} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Harry Buhrman, Matthias Christandl, and Jeroen Zuiddam. Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{buhrman_et_al:LIPIcs.ITCS.2017.24, author = {Buhrman, Harry and Christandl, Matthias and Zuiddam, Jeroen}, title = {{Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {24:1--24:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.24}, URN = {urn:nbn:de:0030-drops-81812}, doi = {10.4230/LIPIcs.ITCS.2017.24}, annote = {Keywords: quantum communication complexity, broadcast channel, number-in-hand, matrix multiplication, support rank} }
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.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} }