Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Prantar Ghosh and Vihan Shah. New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 53:1-53:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ghosh_et_al:LIPIcs.ITCS.2024.53, author = {Ghosh, Prantar and Shah, Vihan}, title = {{New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {53:1--53:22}, 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.53}, URN = {urn:nbn:de:0030-drops-195815}, doi = {10.4230/LIPIcs.ITCS.2024.53}, annote = {Keywords: Graph Algorithms, Streaming, Communication Complexity, Stream Verification, Merlin-Arthur Communication, Lower Bounds} }
Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)
Sepehr Assadi, Nirmit Joshi, Milind Prabhu, and Vihan Shah. Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{assadi_et_al:LIPIcs.ICDT.2023.19, author = {Assadi, Sepehr and Joshi, Nirmit and Prabhu, Milind and Shah, Vihan}, title = {{Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs}}, booktitle = {26th International Conference on Database Theory (ICDT 2023)}, pages = {19:1--19:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-270-9}, ISSN = {1868-8969}, year = {2023}, volume = {255}, editor = {Geerts, Floris and Vandevoort, Brecht}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.19}, URN = {urn:nbn:de:0030-drops-177618}, doi = {10.4230/LIPIcs.ICDT.2023.19}, annote = {Keywords: Streaming algorithms, Quantile summaries, Rank estimation} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Kheeran K. Naidu and Vihan Shah. Space Optimal Vertex Cover in Dynamic Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 53:1-53:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{naidu_et_al:LIPIcs.APPROX/RANDOM.2022.53, author = {Naidu, Kheeran K. and Shah, Vihan}, title = {{Space Optimal Vertex Cover in Dynamic Streams}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {53:1--53:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.53}, URN = {urn:nbn:de:0030-drops-171753}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.53}, annote = {Keywords: Graph Streaming Algorithms, Vertex Cover, Dynamic Streams, Approximation Algorithm} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Sepehr Assadi and Vihan Shah. An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{assadi_et_al:LIPIcs.ITCS.2022.9, author = {Assadi, Sepehr and Shah, Vihan}, title = {{An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {9:1--9:23}, 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.9}, URN = {urn:nbn:de:0030-drops-156054}, doi = {10.4230/LIPIcs.ITCS.2022.9}, annote = {Keywords: Graph streaming algorithms, Sketching, Maximum matching} }