Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)
Hagit Attiya, Pierre Fraigniaud, Ami Paz, and Sergio Rajsbaum. One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{attiya_et_al:LIPIcs.DISC.2023.4, author = {Attiya, Hagit and Fraigniaud, Pierre and Paz, Ami and Rajsbaum, Sergio}, title = {{One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks}}, booktitle = {37th International Symposium on Distributed Computing (DISC 2023)}, pages = {4:1--4:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-301-0}, ISSN = {1868-8969}, year = {2023}, volume = {281}, editor = {Oshman, Rotem}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.4}, URN = {urn:nbn:de:0030-drops-191304}, doi = {10.4230/LIPIcs.DISC.2023.4}, annote = {Keywords: Wait-free computing, lower bounds} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Kyrill Winkler, Ami Paz, Hugo Rincon Galeana, Stefan Schmid, and Ulrich Schmid. The Time Complexity of Consensus Under Oblivious Message Adversaries. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 100:1-100:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{winkler_et_al:LIPIcs.ITCS.2023.100, author = {Winkler, Kyrill and Paz, Ami and Rincon Galeana, Hugo and Schmid, Stefan and Schmid, Ulrich}, title = {{The Time Complexity of Consensus Under Oblivious Message Adversaries}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {100:1--100:28}, 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.100}, URN = {urn:nbn:de:0030-drops-176030}, doi = {10.4230/LIPIcs.ITCS.2023.100}, annote = {Keywords: dynamic networks, oblivious message adversaries, consensus, time complexity} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Monika Henzinger, Ami Paz, and A. R. Sricharan. Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 65:1-65:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{henzinger_et_al:LIPIcs.ESA.2022.65, author = {Henzinger, Monika and Paz, Ami and Sricharan, A. R.}, title = {{Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {65:1--65:14}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.65}, URN = {urn:nbn:de:0030-drops-170035}, doi = {10.4230/LIPIcs.ESA.2022.65}, annote = {Keywords: Dynamic graph algorithms, Expander graphs, Power-law graphs} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Ami Paz and Liat Peterfreund. Playing Guess Who with Your Kids. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 23:1-23:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{paz_et_al:LIPIcs.FUN.2022.23, author = {Paz, Ami and Peterfreund, Liat}, title = {{Playing Guess Who with Your Kids}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {23:1--23:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.23}, URN = {urn:nbn:de:0030-drops-159935}, doi = {10.4230/LIPIcs.FUN.2022.23}, annote = {Keywords: Guess Who?, Binary Search, Error Correcting Codes, Erasure Codes} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Janne H. Korhonen, Ami Paz, Joel Rybicki, Stefan Schmid, and Jukka Suomela. Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 58:1-58:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{korhonen_et_al:LIPIcs.DISC.2021.58, author = {Korhonen, Janne H. and Paz, Ami and Rybicki, Joel and Schmid, Stefan and Suomela, Jukka}, title = {{Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {58:1--58:4}, 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.58}, URN = {urn:nbn:de:0030-drops-148609}, doi = {10.4230/LIPIcs.DISC.2021.58}, annote = {Keywords: Supported LOCAL model, sinkless orientation, round elimination} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, and Ami Paz. Distributed Quantum Proofs for Replicated Data. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{fraigniaud_et_al:LIPIcs.ITCS.2021.28, author = {Fraigniaud, Pierre and Le Gall, Fran\c{c}ois and Nishimura, Harumichi and Paz, Ami}, title = {{Distributed Quantum Proofs for Replicated Data}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {28:1--28: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.28}, URN = {urn:nbn:de:0030-drops-135679}, doi = {10.4230/LIPIcs.ITCS.2021.28}, annote = {Keywords: Quantum Computing, Distributed Network Computing, Algorithmic Aspects of Networks} }
Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)
Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz, and Gregory Schwartzman. Fast Deterministic Algorithms for Highly-Dynamic Networks. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{censorhillel_et_al:LIPIcs.OPODIS.2020.28, author = {Censor-Hillel, Keren and Dafni, Neta and Kolobov, Victor I. and Paz, Ami and Schwartzman, Gregory}, title = {{Fast Deterministic Algorithms for Highly-Dynamic Networks}}, booktitle = {24th International Conference on Principles of Distributed Systems (OPODIS 2020)}, pages = {28:1--28:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-176-4}, ISSN = {1868-8969}, year = {2021}, volume = {184}, editor = {Bramas, Quentin and Oshman, Rotem and Romano, Paolo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.28}, URN = {urn:nbn:de:0030-drops-135138}, doi = {10.4230/LIPIcs.OPODIS.2020.28}, annote = {Keywords: dynamic distributed algorithms} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
Ofer Grossman, Seri Khoury, and Ami Paz. Improved Hardness of Approximation of Diameter in the CONGEST Model. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{grossman_et_al:LIPIcs.DISC.2020.19, author = {Grossman, Ofer and Khoury, Seri and Paz, Ami}, title = {{Improved Hardness of Approximation of Diameter in the CONGEST Model}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {19:1--19:16}, 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.19}, URN = {urn:nbn:de:0030-drops-130972}, doi = {10.4230/LIPIcs.DISC.2020.19}, annote = {Keywords: Distributed graph algorithms, Approximation algorithms, Lower bounds} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
Uri Meir, Ami Paz, and Gregory Schwartzman. Models of Smoothing in Dynamic Networks. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{meir_et_al:LIPIcs.DISC.2020.36, author = {Meir, Uri and Paz, Ami and Schwartzman, Gregory}, title = {{Models of Smoothing in Dynamic Networks}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {36:1--36:16}, 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.36}, URN = {urn:nbn:de:0030-drops-131145}, doi = {10.4230/LIPIcs.DISC.2020.36}, annote = {Keywords: Distributed dynamic graph algorithms, Smoothed analysis, Flooding} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, and Ami Paz. Brief Announcement: Distributed Quantum Proofs for Replicated Data. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 43:1-43:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fraigniaud_et_al:LIPIcs.DISC.2020.43, author = {Fraigniaud, Pierre and Le Gall, Fran\c{c}ois and Nishimura, Harumichi and Paz, Ami}, title = {{Brief Announcement: Distributed Quantum Proofs for Replicated Data}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {43:1--43:3}, 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.43}, URN = {urn:nbn:de:0030-drops-131217}, doi = {10.4230/LIPIcs.DISC.2020.43}, annote = {Keywords: Quantum Computing, Distributed Network Computing, Algorithmic Aspects of Networks} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Pierre Fraigniaud and Ami Paz. The Topology of Local Computing in Networks. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 128:1-128:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fraigniaud_et_al:LIPIcs.ICALP.2020.128, author = {Fraigniaud, Pierre and Paz, Ami}, title = {{The Topology of Local Computing in Networks}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {128:1--128:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.128}, URN = {urn:nbn:de:0030-drops-125358}, doi = {10.4230/LIPIcs.ICALP.2020.128}, annote = {Keywords: Distributed computing, distributed graph algorithms, combinatorial topology} }
Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)
Pierluigi Crescenzi, Pierre Fraigniaud, and Ami Paz. Trade-Offs in Distributed Interactive Proofs. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{crescenzi_et_al:LIPIcs.DISC.2019.13, author = {Crescenzi, Pierluigi and Fraigniaud, Pierre and Paz, Ami}, title = {{Trade-Offs in Distributed Interactive Proofs}}, booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)}, pages = {13:1--13:17}, 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.13}, URN = {urn:nbn:de:0030-drops-113202}, doi = {10.4230/LIPIcs.DISC.2019.13}, annote = {Keywords: Distributed interactive proofs, Distributed verification} }
Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)
Keren Censor-Hillel, Ami Paz, and Noam Ravid. The Sparsest Additive Spanner via Multiple Weighted BFS Trees. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{censorhillel_et_al:LIPIcs.OPODIS.2018.7, author = {Censor-Hillel, Keren and Paz, Ami and Ravid, Noam}, title = {{The Sparsest Additive Spanner via Multiple Weighted BFS Trees}}, booktitle = {22nd International Conference on Principles of Distributed Systems (OPODIS 2018)}, pages = {7:1--7:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-098-9}, ISSN = {1868-8969}, year = {2019}, volume = {125}, editor = {Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.7}, URN = {urn:nbn:de:0030-drops-100676}, doi = {10.4230/LIPIcs.OPODIS.2018.7}, annote = {Keywords: Distributed graph algorithms, congest model, weighted BFS trees, additive spanners} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen, Ami Paz, and Mor Perry. Redundancy in Distributed Proofs. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{feuilloley_et_al:LIPIcs.DISC.2018.24, author = {Feuilloley, Laurent and Fraigniaud, Pierre and Hirvonen, Juho and Paz, Ami and Perry, Mor}, title = {{Redundancy in Distributed Proofs}}, booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)}, pages = {24:1--24:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-092-7}, ISSN = {1868-8969}, year = {2018}, volume = {121}, editor = {Schmid, Ulrich and Widder, Josef}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.24}, URN = {urn:nbn:de:0030-drops-98139}, doi = {10.4230/LIPIcs.DISC.2018.24}, annote = {Keywords: Distributed verification, Distributed graph algorithms, Proof-labeling schemes, Space-time tradeoffs, Non-determinism} }
Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)
Keren Censor-Hillel, Seri Khoury, and Ami Paz. Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{censorhillel_et_al:LIPIcs.DISC.2017.10, author = {Censor-Hillel, Keren and Khoury, Seri and Paz, Ami}, title = {{Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model}}, booktitle = {31st International Symposium on Distributed Computing (DISC 2017)}, pages = {10:1--10:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-053-8}, ISSN = {1868-8969}, year = {2017}, volume = {91}, editor = {Richa, Andr\'{e}a}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.10}, URN = {urn:nbn:de:0030-drops-79969}, doi = {10.4230/LIPIcs.DISC.2017.10}, annote = {Keywords: CONGEST, Lower Bounds, Minimum Vertex Cover, Chromatic Number, Weighted APSP} }
Feedback for Dagstuhl Publishing