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-dev.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 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. Adversarially Robust Coloring for Graph Streams. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 37:1-37:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chakrabarti_et_al:LIPIcs.ITCS.2022.37, author = {Chakrabarti, Amit and Ghosh, Prantar and Stoeckl, Manuel}, title = {{Adversarially Robust Coloring for Graph Streams}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {37:1--37: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.37}, URN = {urn:nbn:de:0030-drops-156332}, doi = {10.4230/LIPIcs.ITCS.2022.37}, annote = {Keywords: Data streaming, graph algorithms, graph coloring, lower bounds, online algorithms} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Prantar Ghosh. New Verification Schemes for Frequency-Based Functions on Data Streams. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{ghosh:LIPIcs.FSTTCS.2020.22, author = {Ghosh, Prantar}, title = {{New Verification Schemes for Frequency-Based Functions on Data Streams}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {22:1--22:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.22}, URN = {urn:nbn:de:0030-drops-132631}, doi = {10.4230/LIPIcs.FSTTCS.2020.22}, annote = {Keywords: data streams, interactive proofs, Arthur-Merlin} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Noga Alon and Sepehr Assadi. Palette Sparsification Beyond (Δ+1) Vertex Coloring. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{alon_et_al:LIPIcs.APPROX/RANDOM.2020.6, author = {Alon, Noga and Assadi, Sepehr}, title = {{Palette Sparsification Beyond (\Delta+1) Vertex Coloring}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {6:1--6:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.6}, URN = {urn:nbn:de:0030-drops-126096}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.6}, annote = {Keywords: Graph coloring, palette sparsification, sublinear algorithms, list-coloring} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Amit Chakrabarti, Prantar Ghosh, and Justin Thaler. Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chakrabarti_et_al:LIPIcs.APPROX/RANDOM.2020.22, author = {Chakrabarti, Amit and Ghosh, Prantar and Thaler, Justin}, title = {{Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {22:1--22:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.22}, URN = {urn:nbn:de:0030-drops-126258}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.22}, annote = {Keywords: data streams, interactive proofs, Arthur-Merlin, graph algorithms} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Suman K. Bera, Amit Chakrabarti, and Prantar Ghosh. Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bera_et_al:LIPIcs.ICALP.2020.11, author = {Bera, Suman K. and Chakrabarti, Amit and Ghosh, Prantar}, title = {{Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {11:1--11:21}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.11}, URN = {urn:nbn:de:0030-drops-124182}, doi = {10.4230/LIPIcs.ICALP.2020.11}, annote = {Keywords: Data streaming, Graph coloring, Sublinear algorithms, Massively parallel communication, Distributed algorithms} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Amit Chakrabarti and Prantar Ghosh. Streaming Verification of Graph Computations via Graph Structure. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 70:1-70:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chakrabarti_et_al:LIPIcs.APPROX-RANDOM.2019.70, author = {Chakrabarti, Amit and Ghosh, Prantar}, title = {{Streaming Verification of Graph Computations via Graph Structure}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {70:1--70:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.70}, URN = {urn:nbn:de:0030-drops-112856}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.70}, annote = {Keywords: data streams, interactive proofs, Arthur-Merlin, graph algorithms} }
Feedback for Dagstuhl Publishing