Published in: Dagstuhl Reports, Volume 12, Issue 9 (2023)
Markus Bläser, Valentine Kabanets, Ronen Shaltiel, and Jacobo Torán. Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371). In Dagstuhl Reports, Volume 12, Issue 9, pp. 41-59, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Article{blaser_et_al:DagRep.12.9.41, author = {Bl\"{a}ser, Markus and Kabanets, Valentine and Shaltiel, Ronen and Tor\'{a}n, Jacobo}, title = {{Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371)}}, pages = {41--59}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {12}, number = {9}, editor = {Bl\"{a}ser, Markus and Kabanets, Valentine and Shaltiel, Ronen and Tor\'{a}n, Jacobo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.9.41}, URN = {urn:nbn:de:0030-drops-178092}, doi = {10.4230/DagRep.12.9.41}, annote = {Keywords: (de-)randomization, algebra, circuits, coding, computational complexity} }
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-dev.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 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 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 1-988, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@Proceedings{blaser_et_al:LIPIcs.STACS.2021, title = {{LIPIcs, Volume 187, STACS 2021, Complete Volume}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {1--988}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021}, URN = {urn:nbn:de:0030-drops-136444}, doi = {10.4230/LIPIcs.STACS.2021}, annote = {Keywords: LIPIcs, Volume 187, STACS 2021, Complete Volume} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{blaser_et_al:LIPIcs.STACS.2021.0, author = {Bl\"{a}ser, Markus and Monmege, Benjamin}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {0:i--0:xvi}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.0}, URN = {urn:nbn:de:0030-drops-136459}, doi = {10.4230/LIPIcs.STACS.2021.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Peter Bürgisser. Optimization, Complexity and Invariant Theory (Invited Talk). In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{burgisser:LIPIcs.STACS.2021.1, author = {B\"{u}rgisser, Peter}, title = {{Optimization, Complexity and Invariant Theory}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {1:1--1:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.1}, URN = {urn:nbn:de:0030-drops-136460}, doi = {10.4230/LIPIcs.STACS.2021.1}, annote = {Keywords: geometric invariant theory, geodesic optimization, non-commutative optimization, null cone, operator scaling, moment polytope, orbit closure intersection, geometric programming} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Patrice Ossona de Mendez. First-Order Transductions of Graphs (Invited Talk). In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 2:1-2:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{ossonademendez:LIPIcs.STACS.2021.2, author = {Ossona de Mendez, Patrice}, title = {{First-Order Transductions of Graphs}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {2:1--2:7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.2}, URN = {urn:nbn:de:0030-drops-136473}, doi = {10.4230/LIPIcs.STACS.2021.2}, annote = {Keywords: Finite model theory, structural graph theory} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Lidia Tendera. On the Fluted Fragment (Invited Talk). In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{tendera:LIPIcs.STACS.2021.3, author = {Tendera, Lidia}, title = {{On the Fluted Fragment}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {3:1--3:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.3}, URN = {urn:nbn:de:0030-drops-136481}, doi = {10.4230/LIPIcs.STACS.2021.3}, annote = {Keywords: decidability, fluted fragment, first-order logic, complexity, satisfiability, non-elementary} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, and Yixin Shen. Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{aggarwal_et_al:LIPIcs.STACS.2021.4, author = {Aggarwal, Divesh and Chen, Yanlin and Kumar, Rajendra and Shen, Yixin}, title = {{Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {4:1--4:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.4}, URN = {urn:nbn:de:0030-drops-136494}, doi = {10.4230/LIPIcs.STACS.2021.4}, annote = {Keywords: Lattices, Shortest Vector Problem, Discrete Gaussian Sampling, Time-Space Tradeoff, Quantum computation, Bounded distance decoding} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. An FPT Algorithm for Elimination Distance to Bounded Degree Graphs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 5:1-5:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{agrawal_et_al:LIPIcs.STACS.2021.5, author = {Agrawal, Akanksha and Kanesh, Lawqueen and Panolan, Fahad and Ramanujan, M. S. and Saurabh, Saket}, title = {{An FPT Algorithm for Elimination Distance to Bounded Degree Graphs}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {5:1--5:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.5}, URN = {urn:nbn:de:0030-drops-136507}, doi = {10.4230/LIPIcs.STACS.2021.5}, annote = {Keywords: Elimination Distance, Fixed-parameter Tractability, Graph Modification} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Simon Apers, András Gilyén, and Stacey Jeffery. A Unified Framework of Quantum Walk Search. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{apers_et_al:LIPIcs.STACS.2021.6, author = {Apers, Simon and Gily\'{e}n, Andr\'{a}s and Jeffery, Stacey}, title = {{A Unified Framework of Quantum Walk Search}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {6:1--6:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.6}, URN = {urn:nbn:de:0030-drops-136511}, doi = {10.4230/LIPIcs.STACS.2021.6}, annote = {Keywords: Quantum Algorithms, Quantum Walks, Graph Theory} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Anna Arutyunova and Melanie Schmidt. Achieving Anonymity via Weak Lower Bound Constraints for k-Median and k-Means. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{arutyunova_et_al:LIPIcs.STACS.2021.7, author = {Arutyunova, Anna and Schmidt, Melanie}, title = {{Achieving Anonymity via Weak Lower Bound Constraints for k-Median and k-Means}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {7:1--7:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.7}, URN = {urn:nbn:de:0030-drops-136529}, doi = {10.4230/LIPIcs.STACS.2021.7}, annote = {Keywords: Clustering with Constraints, lower Bounds, k-Means, Anonymity} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Corentin Barloy and Lorenzo Clemente. Bidimensional Linear Recursive Sequences and Universality of Unambiguous Register Automata. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{barloy_et_al:LIPIcs.STACS.2021.8, author = {Barloy, Corentin and Clemente, Lorenzo}, title = {{Bidimensional Linear Recursive Sequences and Universality of Unambiguous Register Automata}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {8:1--8:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.8}, URN = {urn:nbn:de:0030-drops-136533}, doi = {10.4230/LIPIcs.STACS.2021.8}, annote = {Keywords: unambiguous register automata, universality and inclusion problems, multi-dimensional linear recurrence sequences} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Siddharth Barman, Omar Fawzi, and Paul Fermé. Tight Approximation Guarantees for Concave Coverage Problems. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{barman_et_al:LIPIcs.STACS.2021.9, author = {Barman, Siddharth and Fawzi, Omar and Ferm\'{e}, Paul}, title = {{Tight Approximation Guarantees for Concave Coverage Problems}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {9:1--9:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.9}, URN = {urn:nbn:de:0030-drops-136543}, doi = {10.4230/LIPIcs.STACS.2021.9}, annote = {Keywords: Approximation Algorithms, Coverage Problems, Concave Function} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Libor Barto, Diego Battistelli, and Kevin M. Berg. Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{barto_et_al:LIPIcs.STACS.2021.10, author = {Barto, Libor and Battistelli, Diego and Berg, Kevin M.}, title = {{Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {10:1--10:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.10}, URN = {urn:nbn:de:0030-drops-136557}, doi = {10.4230/LIPIcs.STACS.2021.10}, annote = {Keywords: constraint satisfaction problems, promise constraint satisfaction, Boolean PCSP, polymorphism} }
Feedback for Dagstuhl Publishing