Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Greg Bodwin and Henry Fleischmann. Spanning Adjacency Oracles in Sublinear Time. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 19:1-19:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bodwin_et_al:LIPIcs.ITCS.2024.19, author = {Bodwin, Greg and Fleischmann, Henry}, title = {{Spanning Adjacency Oracles in Sublinear Time}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {19:1--19:21}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.19}, URN = {urn:nbn:de:0030-drops-195475}, doi = {10.4230/LIPIcs.ITCS.2024.19}, annote = {Keywords: Graph algorithms, Sublinear algorithms, Data structures, Graph theory} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Asaf Petruschka, Shay Sapir, and Elad Tzalik. Color Fault-Tolerant Spanners. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 88:1-88:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{petruschka_et_al:LIPIcs.ITCS.2024.88, author = {Petruschka, Asaf and Sapir, Shay and Tzalik, Elad}, title = {{Color Fault-Tolerant Spanners}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {88:1--88:17}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.88}, URN = {urn:nbn:de:0030-drops-196160}, doi = {10.4230/LIPIcs.ITCS.2024.88}, annote = {Keywords: Fault tolerance, Graph spanners} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Shimon Kogan and Merav Parter. Towards Bypassing Lower Bounds for Graph Shortcuts. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 73:1-73:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{kogan_et_al:LIPIcs.ESA.2023.73, author = {Kogan, Shimon and Parter, Merav}, title = {{Towards Bypassing Lower Bounds for Graph Shortcuts}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {73:1--73:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.73}, URN = {urn:nbn:de:0030-drops-187264}, doi = {10.4230/LIPIcs.ESA.2023.73}, annote = {Keywords: Directed Shortcuts, Hopsets, Emulators} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Shimon Kogan and Merav Parter. New Additive Emulators. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 85:1-85:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{kogan_et_al:LIPIcs.ICALP.2023.85, author = {Kogan, Shimon and Parter, Merav}, title = {{New Additive Emulators}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {85:1--85: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.85}, URN = {urn:nbn:de:0030-drops-181377}, doi = {10.4230/LIPIcs.ICALP.2023.85}, annote = {Keywords: Spanners, Emulators, Distance Preservers} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Yael Hitron, Merav Parter, and Eylon Yogev. Secure Distributed Network Optimization Against Eavesdroppers. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 71:1-71:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{hitron_et_al:LIPIcs.ITCS.2023.71, author = {Hitron, Yael and Parter, Merav and Yogev, Eylon}, title = {{Secure Distributed Network Optimization Against Eavesdroppers}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {71:1--71:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.71}, URN = {urn:nbn:de:0030-drops-175746}, doi = {10.4230/LIPIcs.ITCS.2023.71}, annote = {Keywords: congest, secure computation, network optimization} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Yael Hitron, Merav Parter, and Eylon Yogev. Broadcast CONGEST Algorithms Against Eavesdroppers. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 27:1-27:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{hitron_et_al:LIPIcs.DISC.2022.27, author = {Hitron, Yael and Parter, Merav and Yogev, Eylon}, title = {{Broadcast CONGEST Algorithms Against Eavesdroppers}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {27:1--27:19}, 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.27}, URN = {urn:nbn:de:0030-drops-172186}, doi = {10.4230/LIPIcs.DISC.2022.27}, annote = {Keywords: congest, edge-connectivity, secret sharing} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Merav Parter and Asaf Petruschka. Near-Optimal Distributed Computation of Small Vertex Cuts. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 31:1-31:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{parter_et_al:LIPIcs.DISC.2022.31, author = {Parter, Merav and Petruschka, Asaf}, title = {{Near-Optimal Distributed Computation of Small Vertex Cuts}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {31:1--31:21}, 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.31}, URN = {urn:nbn:de:0030-drops-172223}, doi = {10.4230/LIPIcs.DISC.2022.31}, annote = {Keywords: Vertex-connectivity, Congest, Graph Sketches} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Merav Parter and Asaf Petruschka. Õptimal Dual Vertex Failure Connectivity Labels. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 32:1-32:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{parter_et_al:LIPIcs.DISC.2022.32, author = {Parter, Merav and Petruschka, Asaf}, title = {{\~{O}ptimal Dual Vertex Failure Connectivity Labels}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {32:1--32:19}, 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.32}, URN = {urn:nbn:de:0030-drops-172239}, doi = {10.4230/LIPIcs.DISC.2022.32}, annote = {Keywords: Fault-Tolerance, Heavy-Light Decomposition, Labeling Schemes} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Shimon Kogan and Merav Parter. Beating Matrix Multiplication for n^{1/3}-Directed Shortcuts. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 82:1-82:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{kogan_et_al:LIPIcs.ICALP.2022.82, author = {Kogan, Shimon and Parter, Merav}, title = {{Beating Matrix Multiplication for n^\{1/3\}-Directed Shortcuts}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {82:1--82: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.82}, URN = {urn:nbn:de:0030-drops-164230}, doi = {10.4230/LIPIcs.ICALP.2022.82}, annote = {Keywords: Directed Shortcuts, Transitive Closure, Width} }
Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)
Sebastian Forster, Martin Grösbacher, and Tijn de Vos. An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 16:1-16:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{forster_et_al:LIPIcs.OPODIS.2021.16, author = {Forster, Sebastian and Gr\"{o}sbacher, Martin and de Vos, Tijn}, title = {{An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions}}, booktitle = {25th International Conference on Principles of Distributed Systems (OPODIS 2021)}, pages = {16:1--16:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-219-8}, ISSN = {1868-8969}, year = {2022}, volume = {217}, editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.16}, URN = {urn:nbn:de:0030-drops-157914}, doi = {10.4230/LIPIcs.OPODIS.2021.16}, annote = {Keywords: Spanner, low diameter decomposition, synchronizer, distributed graph algorithms} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Yael Hitron and Merav Parter. Broadcast CONGEST Algorithms against Adversarial Edges. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 23:1-23:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{hitron_et_al:LIPIcs.DISC.2021.23, author = {Hitron, Yael and Parter, Merav}, title = {{Broadcast CONGEST Algorithms against Adversarial Edges}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {23:1--23:19}, 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.23}, URN = {urn:nbn:de:0030-drops-148256}, doi = {10.4230/LIPIcs.DISC.2021.23}, annote = {Keywords: CONGEST, Fault-Tolerant Network Design, Edge Connectivity} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Yael Hitron and Merav Parter. General CONGEST Compilers against Adversarial Edges. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 24:1-24:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{hitron_et_al:LIPIcs.DISC.2021.24, author = {Hitron, Yael and Parter, Merav}, title = {{General CONGEST Compilers against Adversarial Edges}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {24:1--24: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.24}, URN = {urn:nbn:de:0030-drops-148266}, doi = {10.4230/LIPIcs.DISC.2021.24}, annote = {Keywords: CONGEST, Cycle Covers, Byzantine Adversaries} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
Yael Hitron, Cameron Musco, and Merav Parter. Spiking Neural Networks Through the Lens of Streaming Algorithms. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 10:1-10:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{hitron_et_al:LIPIcs.DISC.2020.10, author = {Hitron, Yael and Musco, Cameron and Parter, Merav}, title = {{Spiking Neural Networks Through the Lens of Streaming Algorithms}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {10:1--10: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.10}, URN = {urn:nbn:de:0030-drops-130882}, doi = {10.4230/LIPIcs.DISC.2020.10}, annote = {Keywords: Biological distributed algorithms, Spiking neural networks, Streaming algorithms} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
Merav Parter. Distributed Constructions of Dual-Failure Fault-Tolerant Distance Preservers. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 21:1-21:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{parter:LIPIcs.DISC.2020.21, author = {Parter, Merav}, title = {{Distributed Constructions of Dual-Failure Fault-Tolerant Distance Preservers}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {21:1--21:17}, 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.21}, URN = {urn:nbn:de:0030-drops-130992}, doi = {10.4230/LIPIcs.DISC.2020.21}, annote = {Keywords: Fault Tolerance, Distance Preservers, CONGEST} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
Merav Parter. Distributed Planar Reachability in Nearly Optimal Time. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 38:1-38:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{parter:LIPIcs.DISC.2020.38, author = {Parter, Merav}, title = {{Distributed Planar Reachability in Nearly Optimal Time}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {38:1--38:17}, 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.38}, URN = {urn:nbn:de:0030-drops-131160}, doi = {10.4230/LIPIcs.DISC.2020.38}, annote = {Keywords: Distributed Graph Algorithms, Planar Graphs, Reachability} }
Feedback for Dagstuhl Publishing