Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Tomer Ezra, Stefano Leonardi, Michał Pawłowski, Matteo Russo, and Seeun William Umboh. Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 12:1-12:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ezra_et_al:LIPIcs.APPROX/RANDOM.2024.12, author = {Ezra, Tomer and Leonardi, Stefano and Paw{\l}owski, Micha{\l} and Russo, Matteo and Umboh, Seeun William}, title = {{Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {12:1--12:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.12}, URN = {urn:nbn:de:0030-drops-210050}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.12}, annote = {Keywords: Set Cover, Joint Replenishment, TCP-Acknowledgment, Subadditive Function Approximation, Multi-Level Aggregation} }
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 300, 39th Computational Complexity Conference (CCC 2024)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, and Raghuvansh R. Saxena. Information Dissemination via Broadcasts in the Presence of Adversarial Noise. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 19:1-19:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{efremenko_et_al:LIPIcs.CCC.2024.19, author = {Efremenko, Klim and Kol, Gillat and Paramonov, Dmitry and Raz, Ran and Saxena, Raghuvansh R.}, title = {{Information Dissemination via Broadcasts in the Presence of Adversarial Noise}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {19:1--19:33}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.19}, URN = {urn:nbn:de:0030-drops-204159}, doi = {10.4230/LIPIcs.CCC.2024.19}, annote = {Keywords: Radio Networks, Interactive Coding, Error Correcting Codes} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yossi Azar, Shahar Lewkowicz, and Danny Vainstein. List Update with Delays or Time Windows. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{azar_et_al:LIPIcs.ICALP.2024.15, author = {Azar, Yossi and Lewkowicz, Shahar and Vainstein, Danny}, title = {{List Update with Delays or Time Windows}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {15:1--15: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.15}, URN = {urn:nbn:de:0030-drops-201583}, doi = {10.4230/LIPIcs.ICALP.2024.15}, annote = {Keywords: Online, List Update, Delay, Time Window, Deadline} }
Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)
Shay Kutten, Peter Robinson, and Ming Ming Tan. Tight Bounds on the Message Complexity of Distributed Tree Verification. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kutten_et_al:LIPIcs.OPODIS.2023.26, author = {Kutten, Shay and Robinson, Peter and Tan, Ming Ming}, title = {{Tight Bounds on the Message Complexity of Distributed Tree Verification}}, booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)}, pages = {26:1--26:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-308-9}, ISSN = {1868-8969}, year = {2024}, volume = {286}, editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.26}, URN = {urn:nbn:de:0030-drops-195163}, doi = {10.4230/LIPIcs.OPODIS.2023.26}, annote = {Keywords: Distributed Graph Algorithm, Lower Bound} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Fabien Dufoulon, Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. An Almost Singularly Optimal Asynchronous Distributed MST Algorithm. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{dufoulon_et_al:LIPIcs.DISC.2022.19, author = {Dufoulon, Fabien and Kutten, Shay and Moses Jr., William K. and Pandurangan, Gopal and Peleg, David}, title = {{An Almost Singularly Optimal Asynchronous Distributed MST Algorithm}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {19:1--19:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.19}, URN = {urn:nbn:de:0030-drops-172107}, doi = {10.4230/LIPIcs.DISC.2022.19}, annote = {Keywords: Asynchronous networks, Minimum Spanning Tree, Distributed Algorithm, Singularly Optimal} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Yuval Emek, Yuval Gil, and Shay Kutten. Locally Restricted Proof Labeling Schemes. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 20:1-20:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{emek_et_al:LIPIcs.DISC.2022.20, author = {Emek, Yuval and Gil, Yuval and Kutten, Shay}, title = {{Locally Restricted Proof Labeling Schemes}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {20:1--20:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.20}, URN = {urn:nbn:de:0030-drops-172111}, doi = {10.4230/LIPIcs.DISC.2022.20}, annote = {Keywords: proof labeling schemes, generic compilers, SLOCAL algorithms} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. Singularly Near Optimal Leader Election in Asynchronous Networks. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{kutten_et_al:LIPIcs.DISC.2021.27, author = {Kutten, Shay and Moses Jr., William K. and Pandurangan, Gopal and Peleg, David}, title = {{Singularly Near Optimal Leader Election in Asynchronous Networks}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {27:1--27:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.27}, URN = {urn:nbn:de:0030-drops-148294}, doi = {10.4230/LIPIcs.DISC.2021.27}, annote = {Keywords: Leader election, Singular optimality, Randomized algorithms, Asynchronous networks, Arbitrary graphs} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Yuval Emek, Shay Kutten, and Yangguang Shi. Online Paging with a Vanishing Regret. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 67:1-67:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{emek_et_al:LIPIcs.ITCS.2021.67, author = {Emek, Yuval and Kutten, Shay and Shi, Yangguang}, title = {{Online Paging with a Vanishing Regret}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {67:1--67:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.67}, URN = {urn:nbn:de:0030-drops-136065}, doi = {10.4230/LIPIcs.ITCS.2021.67}, annote = {Keywords: online paging, inaccurate predictions, multiple predictors, vanishing regret, full information vs. bandit access} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
Xavier Défago, Yuval Emek, Shay Kutten, Toshimitsu Masuzawa, and Yasumasa Tamura. Communication Efficient Self-Stabilizing Leader Election. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{defago_et_al:LIPIcs.DISC.2020.11, author = {D\'{e}fago, Xavier and Emek, Yuval and Kutten, Shay and Masuzawa, Toshimitsu and Tamura, Yasumasa}, title = {{Communication Efficient Self-Stabilizing Leader Election}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {11:1--11:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-168-9}, ISSN = {1868-8969}, year = {2020}, volume = {179}, editor = {Attiya, Hagit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.11}, URN = {urn:nbn:de:0030-drops-130892}, doi = {10.4230/LIPIcs.DISC.2020.11}, annote = {Keywords: self-stabilization, leader election, communication overhead} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. Singularly Optimal Randomized Leader Election. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kutten_et_al:LIPIcs.DISC.2020.22, author = {Kutten, Shay and Moses Jr., William K. and Pandurangan, Gopal and Peleg, David}, title = {{Singularly Optimal Randomized Leader Election}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {22:1--22:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-168-9}, ISSN = {1868-8969}, year = {2020}, volume = {179}, editor = {Attiya, Hagit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.22}, URN = {urn:nbn:de:0030-drops-131002}, doi = {10.4230/LIPIcs.DISC.2020.22}, annote = {Keywords: Leader election, Asynchronous systems, Randomized algorithms, Singularly optimal, Complete networks} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Yossi Azar, Ashish Chiplunkar, Shay Kutten, and Noam Touitou. Set Cover with Delay - Clairvoyance Is Not Required. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{azar_et_al:LIPIcs.ESA.2020.8, author = {Azar, Yossi and Chiplunkar, Ashish and Kutten, Shay and Touitou, Noam}, title = {{Set Cover with Delay - Clairvoyance Is Not Required}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {8:1--8:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.8}, URN = {urn:nbn:de:0030-drops-128749}, doi = {10.4230/LIPIcs.ESA.2020.8}, annote = {Keywords: Set Cover, Delay, Clairvoyant} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Walter Hussak and Amitabh Trehan. On the Termination of Flooding. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{hussak_et_al:LIPIcs.STACS.2020.17, author = {Hussak, Walter and Trehan, Amitabh}, title = {{On the Termination of Flooding}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {17:1--17:13}, 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.17}, URN = {urn:nbn:de:0030-drops-118786}, doi = {10.4230/LIPIcs.STACS.2020.17}, annote = {Keywords: Flooding algorithm, Network algorithms, Distributed algorithms, Graph theory, Termination, Bipartiteness, Communication, Broadcast} }
Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)
Shimon Bitton, Yuval Emek, Taisuke Izumi, and Shay Kutten. Message Reduction in the LOCAL Model Is a Free Lunch. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bitton_et_al:LIPIcs.DISC.2019.7, author = {Bitton, Shimon and Emek, Yuval and Izumi, Taisuke and Kutten, Shay}, title = {{Message Reduction in the LOCAL Model Is a Free Lunch}}, booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)}, pages = {7:1--7:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-126-9}, ISSN = {1868-8969}, year = {2019}, volume = {146}, editor = {Suomela, Jukka}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.7}, URN = {urn:nbn:de:0030-drops-113145}, doi = {10.4230/LIPIcs.DISC.2019.7}, annote = {Keywords: distributed graph algorithms, spanner, LOCAL model, message complexity} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Yuval Emek, Shay Kutten, Ron Lavi, and Yangguang Shi. Bayesian Generalized Network Design. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{emek_et_al:LIPIcs.ESA.2019.45, author = {Emek, Yuval and Kutten, Shay and Lavi, Ron and Shi, Yangguang}, title = {{Bayesian Generalized Network Design}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {45:1--45:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola 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.2019.45}, URN = {urn:nbn:de:0030-drops-111660}, doi = {10.4230/LIPIcs.ESA.2019.45}, annote = {Keywords: approximation algorithms, Bayesian competitive ratio, Bayesian ignorance, generalized network design, diseconomies of scale, energy consumption, smoothness, best response dynamics} }
Feedback for Dagstuhl Publishing