Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Amit Chakrabarti and Manuel Stoeckl. Finding Missing Items Requires Strong Forms of Randomness. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chakrabarti_et_al:LIPIcs.CCC.2024.28, author = {Chakrabarti, Amit and Stoeckl, Manuel}, title = {{Finding Missing Items Requires Strong Forms of Randomness}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {28:1--28:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.28}, URN = {urn:nbn:de:0030-drops-204242}, doi = {10.4230/LIPIcs.CCC.2024.28}, annote = {Keywords: Data streaming, lower bounds, space complexity, adversarial robustness, derandomization, sketching, sampling} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams. Fast Approximate Counting of Cycles. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{censorhillel_et_al:LIPIcs.ICALP.2024.37, author = {Censor-Hillel, Keren and Even, Tomer and Vassilevska Williams, Virginia}, title = {{Fast Approximate Counting of Cycles}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {37:1--37: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.37}, URN = {urn:nbn:de:0030-drops-201809}, doi = {10.4230/LIPIcs.ICALP.2024.37}, annote = {Keywords: Approximate triangle counting, Approximate cycle counting Fast matrix multiplication, Fast rectangular matrix multiplication} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Talya Eden, Reut Levi, and Dana Ron. Testing C_k-Freeness in Bounded-Arboricity Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 60:1-60:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{eden_et_al:LIPIcs.ICALP.2024.60, author = {Eden, Talya and Levi, Reut and Ron, Dana}, title = {{Testing C\underlinek-Freeness in Bounded-Arboricity Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {60:1--60: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.60}, URN = {urn:nbn:de:0030-drops-202033}, doi = {10.4230/LIPIcs.ICALP.2024.60}, annote = {Keywords: Property Testing, Cycle-Freeness, Bounded Arboricity} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Talya Eden, Jakob Bæk Tejs Houen, Shyam Narayanan, Will Rosenbaum, and Jakub Tětek. Bias Reduction for Sum Estimation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 62:1-62:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{eden_et_al:LIPIcs.APPROX/RANDOM.2023.62, author = {Eden, Talya and Houen, Jakob B{\ae}k Tejs and Narayanan, Shyam and Rosenbaum, Will and T\v{e}tek, Jakub}, title = {{Bias Reduction for Sum Estimation}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {62:1--62:21}, 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.62}, URN = {urn:nbn:de:0030-drops-188872}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.62}, annote = {Keywords: bias reduction, sum estimation, sublinear time algorithms, sample complexity} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, and Adam Smith. Triangle Counting with Local Edge Differential Privacy. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 52:1-52:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{eden_et_al:LIPIcs.ICALP.2023.52, author = {Eden, Talya and Liu, Quanquan C. and Raskhodnikova, Sofya and Smith, Adam}, title = {{Triangle Counting with Local Edge Differential Privacy}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {52:1--52:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.52}, URN = {urn:nbn:de:0030-drops-181048}, doi = {10.4230/LIPIcs.ICALP.2023.52}, annote = {Keywords: local differential privacy, reconstruction attacks, lower bounds, triangle counting} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Ronitt Rubinfeld, and Slobodan Mitrović. Massively Parallel Algorithms for Small Subgraph Counting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 39:1-39:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{biswas_et_al:LIPIcs.APPROX/RANDOM.2022.39, author = {Biswas, Amartya Shankha and Eden, Talya and Liu, Quanquan C. and Rubinfeld, Ronitt and Mitrovi\'{c}, Slobodan}, title = {{Massively Parallel Algorithms for Small Subgraph Counting}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {39:1--39:28}, 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.39}, URN = {urn:nbn:de:0030-drops-171619}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.39}, annote = {Keywords: triangle counting, massively parallel computation, clique counting, approximation algorithms, subgraph counting} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Talya Eden, Dana Ron, and Will Rosenbaum. Almost Optimal Bounds for Sublinear-Time Sampling of k-Cliques in Bounded Arboricity Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 56:1-56:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{eden_et_al:LIPIcs.ICALP.2022.56, author = {Eden, Talya and Ron, Dana and Rosenbaum, Will}, title = {{Almost Optimal Bounds for Sublinear-Time Sampling of k-Cliques in Bounded Arboricity Graphs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {56:1--56:19}, 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.56}, URN = {urn:nbn:de:0030-drops-163974}, doi = {10.4230/LIPIcs.ICALP.2022.56}, annote = {Keywords: sublinear time algorithms, graph algorithms, cliques, arboricity, uniform sampling} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Jakub Tětek. Approximate Triangle Counting via Sampling and Fast Matrix Multiplication. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 107:1-107:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{tetek:LIPIcs.ICALP.2022.107, author = {T\v{e}tek, Jakub}, title = {{Approximate Triangle Counting via Sampling and Fast Matrix Multiplication}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {107:1--107:20}, 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.107}, URN = {urn:nbn:de:0030-drops-164485}, doi = {10.4230/LIPIcs.ICALP.2022.107}, annote = {Keywords: Approximate triangle counting, Fast matrix multiplication, Sampling} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Talya Eden, Piotr Indyk, and Haike Xu. Embeddings and Labeling Schemes for A*. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 62:1-62:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{eden_et_al:LIPIcs.ITCS.2022.62, author = {Eden, Talya and Indyk, Piotr and Xu, Haike}, title = {{Embeddings and Labeling Schemes for A*}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {62:1--62: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.62}, URN = {urn:nbn:de:0030-drops-156585}, doi = {10.4230/LIPIcs.ITCS.2022.62}, annote = {Keywords: A* algorithm, path finding, graph search} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Talya Eden, Saleet Mossel, and Ronitt Rubinfeld. Sampling Multiple Edges Efficiently. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{eden_et_al:LIPIcs.APPROX/RANDOM.2021.51, author = {Eden, Talya and Mossel, Saleet and Rubinfeld, Ronitt}, title = {{Sampling Multiple Edges Efficiently}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {51:1--51:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.51}, URN = {urn:nbn:de:0030-drops-147441}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.51}, annote = {Keywords: Sampling edges, graph algorithm, sublinear algorithms} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Amartya Shankha Biswas, Talya Eden, and Ronitt Rubinfeld. Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 55:1-55:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{biswas_et_al:LIPIcs.APPROX/RANDOM.2021.55, author = {Biswas, Amartya Shankha and Eden, Talya and Rubinfeld, Ronitt}, title = {{Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {55:1--55:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.55}, URN = {urn:nbn:de:0030-drops-147480}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.55}, annote = {Keywords: Sublinear time algorithms, Graph algorithms, Sampling subgraphs, Approximate counting} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma. Erasure-Resilient Sublinear-Time Graph Algorithms. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 80:1-80:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{levi_et_al:LIPIcs.ITCS.2021.80, author = {Levi, Amit and Pallavoor, Ramesh Krishnan S. and Raskhodnikova, Sofya and Varma, Nithin}, title = {{Erasure-Resilient Sublinear-Time Graph Algorithms}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {80:1--80:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.80}, URN = {urn:nbn:de:0030-drops-136192}, doi = {10.4230/LIPIcs.ITCS.2021.80}, annote = {Keywords: Graph property testing, Computing with incomplete information, Approximating graph parameters} }
Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)
Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman. Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{eden_et_al:LIPIcs.DISC.2019.15, author = {Eden, Talya and Fiat, Nimrod and Fischer, Orr and Kuhn, Fabian and Oshman, Rotem}, title = {{Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles}}, booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)}, pages = {15:1--15:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-126-9}, ISSN = {1868-8969}, year = {2019}, volume = {146}, editor = {Suomela, Jukka}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.15}, URN = {urn:nbn:de:0030-drops-113224}, doi = {10.4230/LIPIcs.DISC.2019.15}, annote = {Keywords: Distributed Computing, Subgraph Freeness, CONGEST} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Talya Eden, Dana Ron, and Will Rosenbaum. The Arboricity Captures the Complexity of Sampling Edges. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{eden_et_al:LIPIcs.ICALP.2019.52, author = {Eden, Talya and Ron, Dana and Rosenbaum, Will}, title = {{The Arboricity Captures the Complexity of Sampling Edges}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {52:1--52:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.52}, URN = {urn:nbn:de:0030-drops-106287}, doi = {10.4230/LIPIcs.ICALP.2019.52}, annote = {Keywords: sampling, graph algorithms, arboricity, sublinear-time algorithms} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Talya Eden and Will Rosenbaum. Lower Bounds for Approximating Graph Parameters via Communication Complexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{eden_et_al:LIPIcs.APPROX-RANDOM.2018.11, author = {Eden, Talya and Rosenbaum, Will}, title = {{Lower Bounds for Approximating Graph Parameters via Communication Complexity}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {11:1--11:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.11}, URN = {urn:nbn:de:0030-drops-94156}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.11}, annote = {Keywords: sublinear graph parameter estimation, lower bounds, communication complexity} }