Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Rowan Warneke, Farhana Choudhury, and Anthony Wirth. Maximum Coverage in Random-Arrival Streams. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 102:1-102:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{warneke_et_al:LIPIcs.ESA.2023.102, author = {Warneke, Rowan and Choudhury, Farhana and Wirth, Anthony}, title = {{Maximum Coverage in Random-Arrival Streams}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {102:1--102:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.102}, URN = {urn:nbn:de:0030-drops-187559}, doi = {10.4230/LIPIcs.ESA.2023.102}, annote = {Keywords: Maximum Coverage, Streaming Algorithm, Random Arrival, Greedy Algorithm, Communication Complexity} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Raghavendra Addanki, Andrew McGregor, and Cameron Musco. Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{addanki_et_al:LIPIcs.ESA.2022.2, author = {Addanki, Raghavendra and McGregor, Andrew and Musco, Cameron}, title = {{Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {2:1--2:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.2}, URN = {urn:nbn:de:0030-drops-169400}, doi = {10.4230/LIPIcs.ESA.2022.2}, annote = {Keywords: sublinear graph algorithms, bipartite independent set queries, edge sampling and counting, graph connectivity, query adaptivity} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Andrew McGregor and Rik Sengupta. Graph Reconstruction from Random Subgraphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 96:1-96:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{mcgregor_et_al:LIPIcs.ICALP.2022.96, author = {McGregor, Andrew and Sengupta, Rik}, title = {{Graph Reconstruction from Random Subgraphs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {96:1--96:18}, 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.96}, URN = {urn:nbn:de:0030-drops-164373}, doi = {10.4230/LIPIcs.ICALP.2022.96}, annote = {Keywords: graph reconstruction, sample complexity, deletion channel} }
Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)
Raghavendra Addanki, Andrew McGregor, Alexandra Meliou, and Zafeiria Moumoulidou. Improved Approximation and Scalability for Fair Max-Min Diversification. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{addanki_et_al:LIPIcs.ICDT.2022.7, author = {Addanki, Raghavendra and McGregor, Andrew and Meliou, Alexandra and Moumoulidou, Zafeiria}, title = {{Improved Approximation and Scalability for Fair Max-Min Diversification}}, booktitle = {25th International Conference on Database Theory (ICDT 2022)}, pages = {7:1--7:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-223-5}, ISSN = {1868-8969}, year = {2022}, volume = {220}, editor = {Olteanu, Dan and Vortmeier, Nils}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.7}, URN = {urn:nbn:de:0030-drops-158812}, doi = {10.4230/LIPIcs.ICDT.2022.7}, annote = {Keywords: algorithmic fairness, diversity maximization, data selection, approximation algorithms} }
Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)
Andrew McGregor, David Tench, and Hoa T. Vu. Maximum Coverage in the Data Stream Model: Parameterized and Generalized. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{mcgregor_et_al:LIPIcs.ICDT.2021.12, author = {McGregor, Andrew and Tench, David and Vu, Hoa T.}, title = {{Maximum Coverage in the Data Stream Model: Parameterized and Generalized}}, booktitle = {24th International Conference on Database Theory (ICDT 2021)}, pages = {12:1--12:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-179-5}, ISSN = {1868-8969}, year = {2021}, volume = {186}, editor = {Yi, Ke and Wei, Zhewei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.12}, URN = {urn:nbn:de:0030-drops-137208}, doi = {10.4230/LIPIcs.ICDT.2021.12}, annote = {Keywords: Data streams, maximum coverage, maximum unique coverage, set cover} }
Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)
Zafeiria Moumoulidou, Andrew McGregor, and Alexandra Meliou. Diverse Data Selection under Fairness Constraints. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 13:1-13:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{moumoulidou_et_al:LIPIcs.ICDT.2021.13, author = {Moumoulidou, Zafeiria and McGregor, Andrew and Meliou, Alexandra}, title = {{Diverse Data Selection under Fairness Constraints}}, booktitle = {24th International Conference on Database Theory (ICDT 2021)}, pages = {13:1--13:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-179-5}, ISSN = {1868-8969}, year = {2021}, volume = {186}, editor = {Yi, Ke and Wei, Zhewei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.13}, URN = {urn:nbn:de:0030-drops-137216}, doi = {10.4230/LIPIcs.ICDT.2021.13}, annote = {Keywords: data selection, diversity maximization, fairness constraints, approximation algorithms} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, and Soumyabrata Pal. Trace Reconstruction: Generalized and Parameterized. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 68:1-68:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{krishnamurthy_et_al:LIPIcs.ESA.2019.68, author = {Krishnamurthy, Akshay and Mazumdar, Arya and McGregor, Andrew and Pal, Soumyabrata}, title = {{Trace Reconstruction: Generalized and Parameterized}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {68:1--68:25}, 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.68}, URN = {urn:nbn:de:0030-drops-111891}, doi = {10.4230/LIPIcs.ESA.2019.68}, annote = {Keywords: deletion channel, trace reconstruction, matrix reconstruction} }
Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Andrew McGregor and Sofya Vorotnikova. A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 14:1-14:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{mcgregor_et_al:OASIcs.SOSA.2018.14, author = {McGregor, Andrew and Vorotnikova, Sofya}, title = {{A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs}}, booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)}, pages = {14:1--14:4}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-064-4}, ISSN = {2190-6807}, year = {2018}, volume = {61}, editor = {Seidel, Raimund}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.14}, URN = {urn:nbn:de:0030-drops-82959}, doi = {10.4230/OASIcs.SOSA.2018.14}, annote = {Keywords: data streams, matching, planar graphs, arboricity} }
Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)
Andrew McGregor and Hoa T. Vu. Better Streaming Algorithms for the Maximum Coverage Problem. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{mcgregor_et_al:LIPIcs.ICDT.2017.22, author = {McGregor, Andrew and Vu, Hoa T.}, title = {{Better Streaming Algorithms for the Maximum Coverage Problem}}, booktitle = {20th International Conference on Database Theory (ICDT 2017)}, pages = {22:1--22:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-024-8}, ISSN = {1868-8969}, year = {2017}, volume = {68}, editor = {Benedikt, Michael and Orsi, Giorgio}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.22}, URN = {urn:nbn:de:0030-drops-70620}, doi = {10.4230/LIPIcs.ICDT.2017.22}, annote = {Keywords: algorithms, data streams, approximation, maximum coverage} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Andrew McGregor and Sofya Vorotnikova. Planar Matching in Streams Revisited. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{mcgregor_et_al:LIPIcs.APPROX-RANDOM.2016.17, author = {McGregor, Andrew and Vorotnikova, Sofya}, title = {{Planar Matching in Streams Revisited}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {17:1--17:12}, 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.17}, URN = {urn:nbn:de:0030-drops-66407}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.17}, annote = {Keywords: data streams, planar graphs, arboricity, matchings} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Michael Crouch, Andrew McGregor, Gregory Valiant, and David P. Woodruff. Stochastic Streams: Sample Complexity vs. Space Complexity. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{crouch_et_al:LIPIcs.ESA.2016.32, author = {Crouch, Michael and McGregor, Andrew and Valiant, Gregory and Woodruff, David P.}, title = {{Stochastic Streams: Sample Complexity vs. Space Complexity}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {32:1--32:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.32}, URN = {urn:nbn:de:0030-drops-63838}, doi = {10.4230/LIPIcs.ESA.2016.32}, annote = {Keywords: data streams, sample complexity, frequency moments, graph connectivity, subspace approximation} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian. Verifiable Stream Computation and Arthur–Merlin Communication. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 217-243, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{chakrabarti_et_al:LIPIcs.CCC.2015.217, author = {Chakrabarti, Amit and Cormode, Graham and McGregor, Andrew and Thaler, Justin and Venkatasubramanian, Suresh}, title = {{Verifiable Stream Computation and Arthur–Merlin Communication}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {217--243}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-81-1}, ISSN = {1868-8969}, year = {2015}, volume = {33}, editor = {Zuckerman, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.217}, URN = {urn:nbn:de:0030-drops-50680}, doi = {10.4230/LIPIcs.CCC.2015.217}, annote = {Keywords: Arthur-Merlin communication complexity, streaming interactive proofs} }
Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Andrew McGregor, Atri Rudra, and Steve Uurtamo. Polynomial Fitting of Data Streams with Applications to Codeword Testing. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 428-439, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@InProceedings{mcgregor_et_al:LIPIcs.STACS.2011.428, author = {McGregor, Andrew and Rudra, Atri and Uurtamo, Steve}, title = {{Polynomial Fitting of Data Streams with Applications to Codeword Testing}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {428--439}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.428}, URN = {urn:nbn:de:0030-drops-30322}, doi = {10.4230/LIPIcs.STACS.2011.428}, annote = {Keywords: Streaming, Polynomial Interpolation, Polynomial Regression} }
Feedback for Dagstuhl Publishing