Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Amir Azarmehr and Soheil Behnezhad. Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 14:1-14:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{azarmehr_et_al:LIPIcs.ICALP.2023.14, author = {Azarmehr, Amir and Behnezhad, Soheil}, title = {{Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {14:1--14:15}, 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.14}, URN = {urn:nbn:de:0030-drops-180666}, doi = {10.4230/LIPIcs.ICALP.2023.14}, annote = {Keywords: Maximum Matching, Robust Communication Complexity, Edge Degree Constrained Subgraph} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Jeremiah Blocki, Elena Grigorescu, and Tamalika Mukherjee. Privately Estimating Graph Parameters in Sublinear Time. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 26:1-26:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{blocki_et_al:LIPIcs.ICALP.2022.26, author = {Blocki, Jeremiah and Grigorescu, Elena and Mukherjee, Tamalika}, title = {{Privately Estimating Graph Parameters in Sublinear Time}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {26:1--26:19}, 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.26}, URN = {urn:nbn:de:0030-drops-163674}, doi = {10.4230/LIPIcs.ICALP.2022.26}, annote = {Keywords: differential privacy, sublinear time, graph algorithms} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Sepehr Assadi and Soheil Behnezhad. On the Robust Communication Complexity of Bipartite Matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 48:1-48:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{assadi_et_al:LIPIcs.APPROX/RANDOM.2021.48, author = {Assadi, Sepehr and Behnezhad, Soheil}, title = {{On the Robust Communication Complexity of Bipartite Matching}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {48:1--48:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.48}, URN = {urn:nbn:de:0030-drops-147411}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.48}, annote = {Keywords: Maximum Matching, Communication Complexity, Random-Order Streaming} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Sepehr Assadi and Soheil Behnezhad. Beating Two-Thirds For Random-Order Streaming Matching. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 19:1-19:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{assadi_et_al:LIPIcs.ICALP.2021.19, author = {Assadi, Sepehr and Behnezhad, Soheil}, title = {{Beating Two-Thirds For Random-Order Streaming Matching}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {19:1--19:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.19}, URN = {urn:nbn:de:0030-drops-140887}, doi = {10.4230/LIPIcs.ICALP.2021.19}, annote = {Keywords: Maximum Matching, Streaming, Random-Order Streaming} }
Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, and Hamed Saleh. Brief Announcement: Streaming and Massively Parallel Algorithms for Edge Coloring. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 36:1-36:3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{behnezhad_et_al:LIPIcs.DISC.2019.36, author = {Behnezhad, Soheil and Derakhshan, Mahsa and Hajiaghayi, MohammadTaghi and Knittel, Marina and Saleh, Hamed}, title = {{Brief Announcement: Streaming and Massively Parallel Algorithms for Edge Coloring}}, booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)}, pages = {36:1--36:3}, 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.36}, URN = {urn:nbn:de:0030-drops-113438}, doi = {10.4230/LIPIcs.DISC.2019.36}, annote = {Keywords: Massively Parallel Computation, Streaming, Edge Coloring} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, and Hamed Saleh. Streaming and Massively Parallel Algorithms for Edge Coloring. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 15:1-15:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{behnezhad_et_al:LIPIcs.ESA.2019.15, author = {Behnezhad, Soheil and Derakhshan, Mahsa and Hajiaghayi, MohammadTaghi and Knittel, Marina and Saleh, Hamed}, title = {{Streaming and Massively Parallel Algorithms for Edge Coloring}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {15:1--15:14}, 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.15}, URN = {urn:nbn:de:0030-drops-111361}, doi = {10.4230/LIPIcs.ESA.2019.15}, annote = {Keywords: Massively Parallel Computation, Streaming, Edge Coloring} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, and Vahab Mirrokni. Brief Announcement: MapReduce Algorithms for Massive Trees. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 162:1-162:4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{bateni_et_al:LIPIcs.ICALP.2018.162, author = {Bateni, MohammadHossein and Behnezhad, Soheil and Derakhshan, Mahsa and Hajiaghayi, MohammadTaghi and Mirrokni, Vahab}, title = {{Brief Announcement: MapReduce Algorithms for Massive Trees}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {162:1--162:4}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.162}, URN = {urn:nbn:de:0030-drops-91666}, doi = {10.4230/LIPIcs.ICALP.2018.162}, annote = {Keywords: MapReduce, Trees} }
Feedback for Dagstuhl Publishing