Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Lior Gishboliner, Nick Kushnir, and Asaf Shapira. Testing Versus Estimation of Graph Properties, Revisited. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 46:1-46:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gishboliner_et_al:LIPIcs.APPROX/RANDOM.2023.46, author = {Gishboliner, Lior and Kushnir, Nick and Shapira, Asaf}, title = {{Testing Versus Estimation of Graph Properties, Revisited}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {46:1--46: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.46}, URN = {urn:nbn:de:0030-drops-188713}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.46}, annote = {Keywords: Testing, estimation, weak regularity, randomized algorithms, graph theory, Frieze-Kannan Regularity} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Michael Krivelevich, Tamás Mészáros, Peleg Michaeli, and Clara Shikhelman. Greedy Maximal Independent Sets via Local Limits. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{krivelevich_et_al:LIPIcs.AofA.2020.20, author = {Krivelevich, Michael and M\'{e}sz\'{a}ros, Tam\'{a}s and Michaeli, Peleg and Shikhelman, Clara}, title = {{Greedy Maximal Independent Sets via Local Limits}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {20:1--20:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.20}, URN = {urn:nbn:de:0030-drops-120507}, doi = {10.4230/LIPIcs.AofA.2020.20}, annote = {Keywords: Greedy maximal independent set, random graph, local limit} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Lior Gishboliner, Asaf Shapira, and Henrique Stagni. Testing Linear Inequalities of Subgraph Statistics. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 43:1-43:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{gishboliner_et_al:LIPIcs.ITCS.2020.43, author = {Gishboliner, Lior and Shapira, Asaf and Stagni, Henrique}, title = {{Testing Linear Inequalities of Subgraph Statistics}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {43:1--43:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.43}, URN = {urn:nbn:de:0030-drops-117287}, doi = {10.4230/LIPIcs.ITCS.2020.43}, annote = {Keywords: graph property testing, subgraph statistics} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Lior Gishboliner and Asaf Shapira. Efficient Testing without Efficient Regularity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{gishboliner_et_al:LIPIcs.ITCS.2018.54, author = {Gishboliner, Lior and Shapira, Asaf}, title = {{Efficient Testing without Efficient Regularity}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {54:1--54:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.54}, URN = {urn:nbn:de:0030-drops-83124}, doi = {10.4230/LIPIcs.ITCS.2018.54}, annote = {Keywords: Property testing, Induced C\underline4-freeness} }
Feedback for Dagstuhl Publishing