Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Karl Bringmann, Allan Grønlund, Marvin Künnemann, and Kasper Green Larsen. The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 22:1-22:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bringmann_et_al:LIPIcs.ITCS.2024.22, author = {Bringmann, Karl and Gr{\o}nlund, Allan and K\"{u}nnemann, Marvin and Larsen, Kasper Green}, title = {{The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {22:1--22:25}, 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.22}, URN = {urn:nbn:de:0030-drops-195500}, doi = {10.4230/LIPIcs.ITCS.2024.22}, annote = {Keywords: Fine-grained complexity theory, non-deterministic finite automata} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Amir Abboud, Mina Dalirrooyfard, Ray Li, and Virginia Vassilevska Williams. On Diameter Approximation in Directed Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{abboud_et_al:LIPIcs.ESA.2023.2, author = {Abboud, Amir and Dalirrooyfard, Mina and Li, Ray and Vassilevska Williams, Virginia}, title = {{On Diameter Approximation in Directed Graphs}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {2:1--2:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.2}, URN = {urn:nbn:de:0030-drops-186552}, doi = {10.4230/LIPIcs.ESA.2023.2}, annote = {Keywords: Diameter, Directed Graphs, Approximation Algorithms, Fine-grained complexity} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams, and Zixuan Xu. Faster Detours in Undirected Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{akmal_et_al:LIPIcs.ESA.2023.7, author = {Akmal, Shyan and Vassilevska Williams, Virginia and Williams, Ryan and Xu, Zixuan}, title = {{Faster Detours in Undirected Graphs}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {7:1--7:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.7}, URN = {urn:nbn:de:0030-drops-186601}, doi = {10.4230/LIPIcs.ESA.2023.7}, annote = {Keywords: path finding, detours, parameterized complexity, exact algorithms} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Shyan Akmal and Nicole Wein. A Local-To-Global Theorem for Congested Shortest Paths. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{akmal_et_al:LIPIcs.ESA.2023.8, author = {Akmal, Shyan and Wein, Nicole}, title = {{A Local-To-Global Theorem for Congested Shortest Paths}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {8:1--8:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.8}, URN = {urn:nbn:de:0030-drops-186618}, doi = {10.4230/LIPIcs.ESA.2023.8}, annote = {Keywords: disjoint paths, shortest paths, congestion, parameterized complexity} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Aaron Berger, Jenny Kaufmann, and Virginia Vassilevska Williams. Approximating Min-Diameter: Standard and Bichromatic. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{berger_et_al:LIPIcs.ESA.2023.17, author = {Berger, Aaron and Kaufmann, Jenny and Vassilevska Williams, Virginia}, title = {{Approximating Min-Diameter: Standard and Bichromatic}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {17:1--17:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.17}, URN = {urn:nbn:de:0030-drops-186705}, doi = {10.4230/LIPIcs.ESA.2023.17}, annote = {Keywords: diameter, min distances, fine-grained, approximation algorithm} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Shyan Akmal and Ce Jin. An Efficient Algorithm for All-Pairs Bounded Edge Connectivity. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{akmal_et_al:LIPIcs.ICALP.2023.11, author = {Akmal, Shyan and Jin, Ce}, title = {{An Efficient Algorithm for All-Pairs Bounded Edge Connectivity}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {11:1--11:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.11}, URN = {urn:nbn:de:0030-drops-180632}, doi = {10.4230/LIPIcs.ICALP.2023.11}, annote = {Keywords: maximum flow, all-pairs, connectivity, matrix rank} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Oswin Aichholzer, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, and Nicole Wein. Hardness of Token Swapping on Trees. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{aichholzer_et_al:LIPIcs.ESA.2022.3, author = {Aichholzer, Oswin and Demaine, Erik D. and Korman, Matias and Lubiw, Anna and Lynch, Jayson and Mas\'{a}rov\'{a}, Zuzana and Rudoy, Mikhail and Vassilevska Williams, Virginia and Wein, Nicole}, title = {{Hardness of Token Swapping on Trees}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {3:1--3:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.3}, URN = {urn:nbn:de:0030-drops-169413}, doi = {10.4230/LIPIcs.ESA.2022.3}, annote = {Keywords: Sorting, Token swapping, Trees, NP-hard, Approximation} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Mingyang Deng, Virginia Vassilevska Williams, and Ziqian Zhong. New Lower Bounds and Upper Bounds for Listing Avoidable Vertices. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{deng_et_al:LIPIcs.MFCS.2022.41, author = {Deng, Mingyang and Vassilevska Williams, Virginia and Zhong, Ziqian}, title = {{New Lower Bounds and Upper Bounds for Listing Avoidable Vertices}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {41:1--41:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.41}, URN = {urn:nbn:de:0030-drops-168392}, doi = {10.4230/LIPIcs.MFCS.2022.41}, annote = {Keywords: Avoidable Vertex, Fine-Grained Complexity} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Mingyang Deng, Yael Kirkpatrick, Victor Rong, Virginia Vassilevska Williams, and Ziqian Zhong. New Additive Approximations for Shortest Paths and Cycles. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 50:1-50:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{deng_et_al:LIPIcs.ICALP.2022.50, author = {Deng, Mingyang and Kirkpatrick, Yael and Rong, Victor and Vassilevska Williams, Virginia and Zhong, Ziqian}, title = {{New Additive Approximations for Shortest Paths and Cycles}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {50:1--50:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.50}, URN = {urn:nbn:de:0030-drops-163919}, doi = {10.4230/LIPIcs.ICALP.2022.50}, annote = {Keywords: Fine-grained Complexity, Additive Approximation} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Surya Mathialagan, Virginia Vassilevska Williams, and Yinzhan Xu. Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 94:1-94:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{mathialagan_et_al:LIPIcs.ICALP.2022.94, author = {Mathialagan, Surya and Vassilevska Williams, Virginia and Xu, Yinzhan}, title = {{Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {94:1--94:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.94}, URN = {urn:nbn:de:0030-drops-164359}, doi = {10.4230/LIPIcs.ICALP.2022.94}, annote = {Keywords: All-Pairs Lowest Common Ancestor, Fine-Grained Complexity} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, and Ryan Williams. Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 3:1-3:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{akmal_et_al:LIPIcs.ITCS.2022.3, author = {Akmal, Shyan and Chen, Lijie and Jin, Ce and Raj, Malvika and Williams, Ryan}, title = {{Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {3:1--3:25}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.3}, URN = {urn:nbn:de:0030-drops-155991}, doi = {10.4230/LIPIcs.ITCS.2022.3}, annote = {Keywords: Fine-grained complexity, Merlin-Arthur proofs} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Hung Le, Lazar Milenković, Shay Solomon, and Virginia Vassilevska Williams. Dynamic Matching Algorithms Under Vertex Updates. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 96:1-96:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{le_et_al:LIPIcs.ITCS.2022.96, author = {Le, Hung and Milenkovi\'{c}, Lazar and Solomon, Shay and Vassilevska Williams, Virginia}, title = {{Dynamic Matching Algorithms Under Vertex Updates}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {96:1--96:24}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.96}, URN = {urn:nbn:de:0030-drops-156923}, doi = {10.4230/LIPIcs.ITCS.2022.96}, annote = {Keywords: maximal matching, approximate matching, dynamic algorithm, vertex updates} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Amir Abboud and Virginia Vassilevska Williams. Fine-Grained Hardness for Edit Distance to a Fixed Sequence. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{abboud_et_al:LIPIcs.ICALP.2021.7, author = {Abboud, Amir and Vassilevska Williams, Virginia}, title = {{Fine-Grained Hardness for Edit Distance to a Fixed Sequence}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {7:1--7:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.7}, URN = {urn:nbn:de:0030-drops-140768}, doi = {10.4230/LIPIcs.ICALP.2021.7}, annote = {Keywords: SAT, edit distance, fine-grained complexity, conditional lower bound, sequence alignment} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Shyan Akmal and Ce Jin. Faster Algorithms for Bounded Tree Edit Distance. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{akmal_et_al:LIPIcs.ICALP.2021.12, author = {Akmal, Shyan and Jin, Ce}, title = {{Faster Algorithms for Bounded Tree Edit Distance}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {12:1--12:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.12}, URN = {urn:nbn:de:0030-drops-140819}, doi = {10.4230/LIPIcs.ICALP.2021.12}, annote = {Keywords: tree edit distance, edit distance, dynamic programming} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Shyan Akmal and Virginia Vassilevska Williams. Improved Approximation for Longest Common Subsequence over Small Alphabets. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{akmal_et_al:LIPIcs.ICALP.2021.13, author = {Akmal, Shyan and Vassilevska Williams, Virginia}, title = {{Improved Approximation for Longest Common Subsequence over Small Alphabets}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {13:1--13:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.13}, URN = {urn:nbn:de:0030-drops-140821}, doi = {10.4230/LIPIcs.ICALP.2021.13}, annote = {Keywords: approximation algorithms, longest common subsequence, subquadratic} }
Feedback for Dagstuhl Publishing