LIPIcs, Volume 261
ICALP 2023, July 10-14, 2023, Paderborn, Germany
Editors: Kousha Etessami, Uriel Feige, and Gabriele Puppis
Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)
Ramtin Afshar, Michael Dillencourt, Michael T. Goodrich, and Evrim Ozel. Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 8:1-8:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{afshar_et_al:LIPIcs.SEA.2023.8, author = {Afshar, Ramtin and Dillencourt, Michael and Goodrich, Michael T. and Ozel, Evrim}, title = {{Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors}}, booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)}, pages = {8:1--8:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-279-2}, ISSN = {1868-8969}, year = {2023}, volume = {265}, editor = {Georgiadis, Loukas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.8}, URN = {urn:nbn:de:0030-drops-183585}, doi = {10.4230/LIPIcs.SEA.2023.8}, annote = {Keywords: sorting, algorithms, randomization, experimentation} }
Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)
Stephen Jaud, Anthony Wirth, and Farhana Choudhury. Maximum Coverage in Sublinear Space, Faster. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 21:1-21:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{jaud_et_al:LIPIcs.SEA.2023.21, author = {Jaud, Stephen and Wirth, Anthony and Choudhury, Farhana}, title = {{Maximum Coverage in Sublinear Space, Faster}}, booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)}, pages = {21:1--21:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-279-2}, ISSN = {1868-8969}, year = {2023}, volume = {265}, editor = {Georgiadis, Loukas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.21}, URN = {urn:nbn:de:0030-drops-183715}, doi = {10.4230/LIPIcs.SEA.2023.21}, annote = {Keywords: streaming algorithms, subsampling, maximum set cover, k-wise independent hash functions} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 1-2486, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@Proceedings{etessami_et_al:LIPIcs.ICALP.2023, title = {{LIPIcs, Volume 261, ICALP 2023, Complete Volume}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {1--2486}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023}, URN = {urn:nbn:de:0030-drops-180517}, doi = {10.4230/LIPIcs.ICALP.2023}, annote = {Keywords: LIPIcs, Volume 261, ICALP 2023, Complete Volume} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 0:i-0:xxxviii, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{etessami_et_al:LIPIcs.ICALP.2023.0, author = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {0:i--0:xxxviii}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.0}, URN = {urn:nbn:de:0030-drops-180523}, doi = {10.4230/LIPIcs.ICALP.2023.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Anna R. Karlin. A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{karlin:LIPIcs.ICALP.2023.1, author = {Karlin, Anna R.}, title = {{A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {1:1--1:1}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.1}, URN = {urn:nbn:de:0030-drops-180531}, doi = {10.4230/LIPIcs.ICALP.2023.1}, annote = {Keywords: Traveling Salesperson Problem, approximation algorithm} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Rasmus Kyng. An Almost-Linear Time Algorithm for Maximum Flow and More (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, p. 2:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{kyng:LIPIcs.ICALP.2023.2, author = {Kyng, Rasmus}, title = {{An Almost-Linear Time Algorithm for Maximum Flow and More}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {2:1--2:1}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.2}, URN = {urn:nbn:de:0030-drops-180543}, doi = {10.4230/LIPIcs.ICALP.2023.2}, annote = {Keywords: Maximum flow, Minimum cost flow, Data structures, Interior point methods, Convex optimization} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Pascal Baumann, Moses Ganardi, Rupak Majumdar, Ramanathan S. Thinniyam, and Georg Zetzsche. Context-Bounded Analysis of Concurrent Programs (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 3:1-3:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{baumann_et_al:LIPIcs.ICALP.2023.3, author = {Baumann, Pascal and Ganardi, Moses and Majumdar, Rupak and Thinniyam, Ramanathan S. and Zetzsche, Georg}, title = {{Context-Bounded Analysis of Concurrent Programs}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {3:1--3:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.3}, URN = {urn:nbn:de:0030-drops-180559}, doi = {10.4230/LIPIcs.ICALP.2023.3}, annote = {Keywords: Context-bounded analysis, Multi-threaded programs, Decidability} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Thomas Vidick. Quantum Codes, Local Testability and Interactive Proofs: State of the Art and Open Questions (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, p. 4:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{vidick:LIPIcs.ICALP.2023.4, author = {Vidick, Thomas}, title = {{Quantum Codes, Local Testability and Interactive Proofs: State of the Art and Open Questions}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {4:1--4:1}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.4}, URN = {urn:nbn:de:0030-drops-180569}, doi = {10.4230/LIPIcs.ICALP.2023.4}, annote = {Keywords: quantum interactive proofs, quantum codes} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
James Worrell. The Skolem Landscape (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 5:1-5:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{worrell:LIPIcs.ICALP.2023.5, author = {Worrell, James}, title = {{The Skolem Landscape}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {5:1--5:2}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.5}, URN = {urn:nbn:de:0030-drops-180573}, doi = {10.4230/LIPIcs.ICALP.2023.5}, annote = {Keywords: Automata, Formal Languages, Linear Recurrence Sequences} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Anders Aamand, Adam Karczmarz, Jakub Łącki, Nikos Parotsidis, Peter M. R. Rasmussen, and Mikkel Thorup. Optimal Decremental Connectivity in Non-Sparse Graphs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 6:1-6:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{aamand_et_al:LIPIcs.ICALP.2023.6, author = {Aamand, Anders and Karczmarz, Adam and {\L}\k{a}cki, Jakub and Parotsidis, Nikos and Rasmussen, Peter M. R. and Thorup, Mikkel}, title = {{Optimal Decremental Connectivity in Non-Sparse Graphs}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {6:1--6:17}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.6}, URN = {urn:nbn:de:0030-drops-180581}, doi = {10.4230/LIPIcs.ICALP.2023.6}, annote = {Keywords: decremental connectivity, dynamic connectivity} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Peyman Afshani, Pingan Cheng, Aniket Basu Roy, and Zhewei Wei. On Range Summary Queries. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 7:1-7:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{afshani_et_al:LIPIcs.ICALP.2023.7, author = {Afshani, Peyman and Cheng, Pingan and Basu Roy, Aniket and Wei, Zhewei}, title = {{On Range Summary Queries}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {7:1--7:17}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.7}, URN = {urn:nbn:de:0030-drops-180590}, doi = {10.4230/LIPIcs.ICALP.2023.7}, annote = {Keywords: Computational Geometry, Range Searching, Random Sampling, Geometric Approximation, Data Structures and Algorithms} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Ishan Agarwal and Richard Cole. Stable Matching: Choosing Which Proposals to Make. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 8:1-8:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{agarwal_et_al:LIPIcs.ICALP.2023.8, author = {Agarwal, Ishan and Cole, Richard}, title = {{Stable Matching: Choosing Which Proposals to Make}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {8:1--8: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.8}, URN = {urn:nbn:de:0030-drops-180603}, doi = {10.4230/LIPIcs.ICALP.2023.8}, annote = {Keywords: Stable matching, randomized analysis} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Daniel Agassy, Dani Dorfman, and Haim Kaplan. Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 9:1-9:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{agassy_et_al:LIPIcs.ICALP.2023.9, author = {Agassy, Daniel and Dorfman, Dani and Kaplan, Haim}, title = {{Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {9:1--9: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.9}, URN = {urn:nbn:de:0030-drops-180619}, doi = {10.4230/LIPIcs.ICALP.2023.9}, annote = {Keywords: Exapander Decomposition, Cut-Matching Game} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, Joona Särkijärvi, and Jukka Suomela. Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 10:1-10:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{akbari_et_al:LIPIcs.ICALP.2023.10, author = {Akbari, Amirreza and Eslami, Navid and Lievonen, Henrik and Melnyk, Darya and S\"{a}rkij\"{a}rvi, Joona and Suomela, Jukka}, title = {{Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {10:1--10: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.10}, URN = {urn:nbn:de:0030-drops-180627}, doi = {10.4230/LIPIcs.ICALP.2023.10}, annote = {Keywords: Online computation, spatial advice, distributed algorithms, computational complexity} }
Feedback for Dagstuhl Publishing