Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, and Sagnik Mukhopadhyay. Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{assadi_et_al:LIPIcs.CCC.2024.7, author = {Assadi, Sepehr and Ghosh, Prantar and Loff, Bruno and Mittal, Parth and Mukhopadhyay, Sagnik}, title = {{Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {7:1--7:16}, 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.7}, URN = {urn:nbn:de:0030-drops-204035}, doi = {10.4230/LIPIcs.CCC.2024.7}, annote = {Keywords: Graph streaming, Lower bounds, Communication complexity, k-Cores and degeneracy} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
S M Ferdous, Alex Pothen, and Mahantesh Halappanavar. Streaming Matching and Edge Cover in Practice. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ferdous_et_al:LIPIcs.SEA.2024.12, author = {Ferdous, S M and Pothen, Alex and Halappanavar, Mahantesh}, title = {{Streaming Matching and Edge Cover in Practice}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {12:1--12:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.12}, URN = {urn:nbn:de:0030-drops-203773}, doi = {10.4230/LIPIcs.SEA.2024.12}, annote = {Keywords: Matching, Edge Cover, Semi-Streaming Algorithm, Parallel Algorithms, Algorithm Engineering} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Prantar Ghosh and Manuel Stoeckl. Low-Memory Algorithms for Online Edge Coloring. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 71:1-71:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ghosh_et_al:LIPIcs.ICALP.2024.71, author = {Ghosh, Prantar and Stoeckl, Manuel}, title = {{Low-Memory Algorithms for Online Edge Coloring}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {71:1--71: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.71}, URN = {urn:nbn:de:0030-drops-202146}, doi = {10.4230/LIPIcs.ICALP.2024.71}, annote = {Keywords: Edge coloring, streaming model, online algorithms} }
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)
Uri Meir. Comparison Graphs: A Unified Method for Uniformity Testing. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{meir:LIPIcs.ITCS.2021.17, author = {Meir, Uri}, title = {{Comparison Graphs: A Unified Method for Uniformity Testing}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {17:1--17: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.17}, URN = {urn:nbn:de:0030-drops-135560}, doi = {10.4230/LIPIcs.ITCS.2021.17}, annote = {Keywords: Distribution Testing, Uniformity Testing, Distributed Algorithms, Streaming Algorithms, Comparison Graphs} }
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} }