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 137, 34th Computational Complexity Conference (CCC 2019)
Kaave Hosseini, Shachar Lovett, and Grigory Yaroslavtsev. Optimality of Linear Sketching Under Modular Updates. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{hosseini_et_al:LIPIcs.CCC.2019.13, author = {Hosseini, Kaave and Lovett, Shachar and Yaroslavtsev, Grigory}, title = {{Optimality of Linear Sketching Under Modular Updates}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {13:1--13:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.13}, URN = {urn:nbn:de:0030-drops-108355}, doi = {10.4230/LIPIcs.CCC.2019.13}, annote = {Keywords: communication complexity, linear sketching, streaming algorithm} }
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 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: 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} }
Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Sepehr Assadi, Sanjeev Khanna, Yang Li, and Val Tannen. Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 52-68, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{assadi_et_al:LIPIcs.FSTTCS.2015.52, author = {Assadi, Sepehr and Khanna, Sanjeev and Li, Yang and Tannen, Val}, title = {{Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches}}, booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)}, pages = {52--68}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-97-2}, ISSN = {1868-8969}, year = {2015}, volume = {45}, editor = {Harsha, Prahladh and Ramalingam, G.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.52}, URN = {urn:nbn:de:0030-drops-56361}, doi = {10.4230/LIPIcs.FSTTCS.2015.52}, annote = {Keywords: Small-space Algorithms, Maximum Matchings, Vertex Sparsifiers} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Xiaoming Sun and David P. Woodruff. Tight Bounds for Graph Problems in Insertion Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 435-448, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{sun_et_al:LIPIcs.APPROX-RANDOM.2015.435, author = {Sun, Xiaoming and Woodruff, David P.}, title = {{Tight Bounds for Graph Problems in Insertion Streams}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {435--448}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.435}, URN = {urn:nbn:de:0030-drops-53160}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.435}, annote = {Keywords: communication complexity, data streams, graphs, space complexity} }
Feedback for Dagstuhl Publishing