Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond. Local Certification of Geometric Graph Classes. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{defrain_et_al:LIPIcs.MFCS.2024.48, author = {Defrain, Oscar and Esperet, Louis and Lagoutte, Aur\'{e}lie and Morin, Pat and Raymond, Jean-Florent}, title = {{Local Certification of Geometric Graph Classes}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {48:1--48:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.48}, URN = {urn:nbn:de:0030-drops-206042}, doi = {10.4230/LIPIcs.MFCS.2024.48}, annote = {Keywords: Local certification, proof labeling schemes, geometric intersection graphs} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Surender Baswana and Koustav Bhanja. Vital Edges for (s,t)-Mincut: Efficient Algorithms, Compact Structures, & Optimal Sensitivity Oracles. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{baswana_et_al:LIPIcs.ICALP.2024.17, author = {Baswana, Surender and Bhanja, Koustav}, title = {{Vital Edges for (s,t)-Mincut: Efficient Algorithms, Compact Structures, \& Optimal Sensitivity Oracles}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {17:1--17:20}, 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.17}, URN = {urn:nbn:de:0030-drops-201601}, doi = {10.4230/LIPIcs.ICALP.2024.17}, annote = {Keywords: maxflow, vital edges, graph algorithms, structures, st-cuts, sensitivity oracle} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, and Maksim Zhukovskii. Tight Bounds on Adjacency Labels for Monotone Graph Classes. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bonnet_et_al:LIPIcs.ICALP.2024.31, author = {Bonnet, \'{E}douard and Duron, Julien and Sylvester, John and Zamaraev, Viktor and Zhukovskii, Maksim}, title = {{Tight Bounds on Adjacency Labels for Monotone Graph Classes}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {31:1--31:20}, 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.31}, URN = {urn:nbn:de:0030-drops-201741}, doi = {10.4230/LIPIcs.ICALP.2024.31}, annote = {Keywords: Adjacency labeling, degeneracy, monotone classes, small classes, factorial classes, implicit graph conjecture} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Ilan Doron-Arad and Joseph (Seffi) Naor. Non-Linear Paging. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 57:1-57:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{doronarad_et_al:LIPIcs.ICALP.2024.57, author = {Doron-Arad, Ilan and Naor, Joseph (Seffi)}, title = {{Non-Linear Paging}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {57:1--57:19}, 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.57}, URN = {urn:nbn:de:0030-drops-202000}, doi = {10.4230/LIPIcs.ICALP.2024.57}, annote = {Keywords: paging, competitive analysis, non-linear paging, submodular and supermodular functions} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yaniv Sadeh and Haim Kaplan. Caching Connections in Matchings. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 120:1-120:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{sadeh_et_al:LIPIcs.ICALP.2024.120, author = {Sadeh, Yaniv and Kaplan, Haim}, title = {{Caching Connections in Matchings}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {120:1--120:20}, 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.120}, URN = {urn:nbn:de:0030-drops-202639}, doi = {10.4230/LIPIcs.ICALP.2024.120}, annote = {Keywords: Caching, Matchings, Caching in Matchings, Edge Coloring, Online Algorithms} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Brieuc Guinard and Amos Korman. Tight Bounds for the Cover Times of Random Walks with Heterogeneous Step Lengths. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{guinard_et_al:LIPIcs.STACS.2020.28, author = {Guinard, Brieuc and Korman, Amos}, title = {{Tight Bounds for the Cover Times of Random Walks with Heterogeneous Step Lengths}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {28:1--28:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.28}, URN = {urn:nbn:de:0030-drops-118892}, doi = {10.4230/LIPIcs.STACS.2020.28}, annote = {Keywords: Computational Biology, Randomness in Computing, Search Algorithms, Random Walks, L\'{e}vy Flights, Intermittent Search, CCRW} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Amos Korman and Yoav Rodeh. Multi-Round Cooperative Search Games with Multiple Players. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 146:1-146:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{korman_et_al:LIPIcs.ICALP.2019.146, author = {Korman, Amos and Rodeh, Yoav}, title = {{Multi-Round Cooperative Search Games with Multiple Players}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {146:1--146:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.146}, URN = {urn:nbn:de:0030-drops-107227}, doi = {10.4230/LIPIcs.ICALP.2019.146}, annote = {Keywords: Algorithmic Mechanism Design, Parallel Algorithms, Collaborative Search, Fault-Tolerance, Price of Anarchy, Price of Stability, Symmetric Equilibria} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Lucas Boczkowski, Amos Korman, and Yoav Rodeh. Searching a Tree with Permanently Noisy Advice. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 54:1-54:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{boczkowski_et_al:LIPIcs.ESA.2018.54, author = {Boczkowski, Lucas and Korman, Amos and Rodeh, Yoav}, title = {{Searching a Tree with Permanently Noisy Advice}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {54:1--54:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.54}, URN = {urn:nbn:de:0030-drops-95176}, doi = {10.4230/LIPIcs.ESA.2018.54}, annote = {Keywords: Data structures, Graph search, Average Case Analysis} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Lucas Boczkowski, Ofer Feinerman, Amos Korman, and Emanuele Natale. Limits for Rumor Spreading in Stochastic Populations. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 49:1-49:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{boczkowski_et_al:LIPIcs.ITCS.2018.49, author = {Boczkowski, Lucas and Feinerman, Ofer and Korman, Amos and Natale, Emanuele}, title = {{Limits for Rumor Spreading in Stochastic Populations}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {49:1--49:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.49}, URN = {urn:nbn:de:0030-drops-83207}, doi = {10.4230/LIPIcs.ITCS.2018.49}, annote = {Keywords: Noisy communication, Passive communication, Ant recruitment, Hypothesis testing} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Amos Korman and Yoav Rodeh. The Dependent Doors Problem: An Investigation into Sequential Decisions without Feedback. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 81:1-81:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{korman_et_al:LIPIcs.ICALP.2017.81, author = {Korman, Amos and Rodeh, Yoav}, title = {{The Dependent Doors Problem: An Investigation into Sequential Decisions without Feedback}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {81:1--81:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.81}, URN = {urn:nbn:de:0030-drops-73738}, doi = {10.4230/LIPIcs.ICALP.2017.81}, annote = {Keywords: No Feedback, Sequential Decisions, Probabilistic Environment, Exploration and Exploitation, Golden Ratio} }
Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Liah Kor, Amos Korman, and David Peleg. Tight Bounds For Distributed MST Verification. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 69-80, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@InProceedings{kor_et_al:LIPIcs.STACS.2011.69, author = {Kor, Liah and Korman, Amos and Peleg, David}, title = {{Tight Bounds For Distributed MST Verification}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {69--80}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.69}, URN = {urn:nbn:de:0030-drops-30000}, doi = {10.4230/LIPIcs.STACS.2011.69}, annote = {Keywords: distributed algorithms, distributed verification, labeling schemes, minimum-weight spanning tree} }
Feedback for Dagstuhl Publishing