Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Diba Hashemi and Weronika Wrzos-Kaminska. Weighted Matching in the Random-Order Streaming and Robust Communication Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 16:1-16:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hashemi_et_al:LIPIcs.APPROX/RANDOM.2024.16, author = {Hashemi, Diba and Wrzos-Kaminska, Weronika}, title = {{Weighted Matching in the Random-Order Streaming and Robust Communication Models}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {16:1--16:26}, 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.16}, URN = {urn:nbn:de:0030-drops-210097}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.16}, annote = {Keywords: Maximum Weight Matching, Streaming, Random-Order Streaming, Robust Communication Complexity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yu Chen, Michael Kapralov, Mikhail Makarov, and Davide Mazzali. On the Streaming Complexity of Expander Decomposition. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ICALP.2024.46, author = {Chen, Yu and Kapralov, Michael and Makarov, Mikhail and Mazzali, Davide}, title = {{On the Streaming Complexity of Expander Decomposition}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {46:1--46: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.46}, URN = {urn:nbn:de:0030-drops-201890}, doi = {10.4230/LIPIcs.ICALP.2024.46}, annote = {Keywords: Graph Sketching, Dynamic Streaming, Expander Decomposition} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Agastya Vibhuti Jha and Akash Kumar. A Sublinear Time Tester for Max-Cut on Clusterable Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 91:1-91:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{jha_et_al:LIPIcs.ICALP.2024.91, author = {Jha, Agastya Vibhuti and Kumar, Akash}, title = {{A Sublinear Time Tester for Max-Cut on Clusterable Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {91:1--91:17}, 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.91}, URN = {urn:nbn:de:0030-drops-202344}, doi = {10.4230/LIPIcs.ICALP.2024.91}, annote = {Keywords: Sublinear Algorithms, Graph Algorithms, Clusterable Graphs, Property Testung} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Ce Jin, Michael Kapralov, Sepideh Mahabadi, and Ali Vakilian. Streaming Algorithms for Connectivity Augmentation. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 93:1-93:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{jin_et_al:LIPIcs.ICALP.2024.93, author = {Jin, Ce and Kapralov, Michael and Mahabadi, Sepideh and Vakilian, Ali}, title = {{Streaming Algorithms for Connectivity Augmentation}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {93:1--93: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.93}, URN = {urn:nbn:de:0030-drops-202367}, doi = {10.4230/LIPIcs.ICALP.2024.93}, annote = {Keywords: streaming algorithms, connectivity augmentation} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Sepehr Assadi, Michael Kapralov, and Huacheng Yu. On Constructing Spanners from Random Gaussian Projections. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 57:1-57:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{assadi_et_al:LIPIcs.APPROX/RANDOM.2023.57, author = {Assadi, Sepehr and Kapralov, Michael and Yu, Huacheng}, title = {{On Constructing Spanners from Random Gaussian Projections}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {57:1--57:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.57}, URN = {urn:nbn:de:0030-drops-188821}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.57}, annote = {Keywords: sketching algorithm, lower bound, graph spanner} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Arnold Filtser, Michael Kapralov, and Mikhail Makarov. Expander Decomposition in Dynamic Streams. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 50:1-50:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{filtser_et_al:LIPIcs.ITCS.2023.50, author = {Filtser, Arnold and Kapralov, Michael and Makarov, Mikhail}, title = {{Expander Decomposition in Dynamic Streams}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {50:1--50:13}, 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.50}, URN = {urn:nbn:de:0030-drops-175534}, doi = {10.4230/LIPIcs.ITCS.2023.50}, annote = {Keywords: Streaming, expander decomposition, graph sparsifiers} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, and Samson Zhou. Noisy Boolean Hidden Matching with Applications. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 91:1-91:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kapralov_et_al:LIPIcs.ITCS.2022.91, author = {Kapralov, Michael and Musipatla, Amulya and Tardos, Jakab and Woodruff, David P. and Zhou, Samson}, title = {{Noisy Boolean Hidden Matching with Applications}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {91:1--91:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.91}, URN = {urn:nbn:de:0030-drops-156876}, doi = {10.4230/LIPIcs.ITCS.2022.91}, annote = {Keywords: Boolean Hidden Matching, Lower Bounds, Communication Complexity, Streaming Algorithms} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Sepehr Assadi, Michael Kapralov, and Sanjeev Khanna. A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{assadi_et_al:LIPIcs.ITCS.2019.6, author = {Assadi, Sepehr and Kapralov, Michael and Khanna, Sanjeev}, title = {{A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {6:1--6:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.6}, URN = {urn:nbn:de:0030-drops-100996}, doi = {10.4230/LIPIcs.ITCS.2019.6}, annote = {Keywords: Sublinear-time algorithms, Subgraph counting, AGM bound} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Sepehr Assadi and Aaron Bernstein. Towards a Unified Theory of Sparsification for Matching Problems. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{assadi_et_al:OASIcs.SOSA.2019.11, author = {Assadi, Sepehr and Bernstein, Aaron}, title = {{Towards a Unified Theory of Sparsification for Matching Problems}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {11:1--11:20}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.11}, URN = {urn:nbn:de:0030-drops-100370}, doi = {10.4230/OASIcs.SOSA.2019.11}, annote = {Keywords: Maximum matching, matching sparsifiers, one-way communication complexity, stochastic matching, fault-tolerant matching} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Michael B. Cohen, Cameron Musco, and Jakub Pachocki. Online Row Sampling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{cohen_et_al:LIPIcs.APPROX-RANDOM.2016.7, author = {Cohen, Michael B. and Musco, Cameron and Pachocki, Jakub}, title = {{Online Row Sampling}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {7:1--7:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.7}, URN = {urn:nbn:de:0030-drops-66304}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.7}, annote = {Keywords: spectral sparsification, leverage score sampling, online sparsification} }
Feedback for Dagstuhl Publishing