Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova, and Dragos Ristache. Testing Connectedness of Images. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 66:1-66:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{berman_et_al:LIPIcs.APPROX/RANDOM.2023.66, author = {Berman, Piotr and Murzabulatov, Meiram and Raskhodnikova, Sofya and Ristache, Dragos}, title = {{Testing Connectedness of Images}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {66:1--66:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.66}, URN = {urn:nbn:de:0030-drops-188918}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.66}, annote = {Keywords: Property testing, sublinear-algorithms, lower bounds, connectivity, graphs} }
Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. The Power and Limitations of Uniform Samples in Testing Properties of Figures. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{berman_et_al:LIPIcs.FSTTCS.2016.45, author = {Berman, Piotr and Murzabulatov, Meiram and Raskhodnikova, Sofya}, title = {{The Power and Limitations of Uniform Samples in Testing Properties of Figures}}, booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)}, pages = {45:1--45:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-027-9}, ISSN = {1868-8969}, year = {2016}, volume = {65}, editor = {Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.45}, URN = {urn:nbn:de:0030-drops-68803}, doi = {10.4230/LIPIcs.FSTTCS.2016.45}, annote = {Keywords: Property testing, randomized algorithms, being a half-plane, convexity} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. Tolerant Testers of Image Properties. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 90:1-90:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{berman_et_al:LIPIcs.ICALP.2016.90, author = {Berman, Piotr and Murzabulatov, Meiram and Raskhodnikova, Sofya}, title = {{Tolerant Testers of Image Properties}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {90:1--90:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.90}, URN = {urn:nbn:de:0030-drops-61959}, doi = {10.4230/LIPIcs.ICALP.2016.90}, annote = {Keywords: Computational geometry, convexity, half-plane, connectedness, propertytesting, tolerant property testing} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. Testing Convexity of Figures Under the Uniform Distribution. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{berman_et_al:LIPIcs.SoCG.2016.17, author = {Berman, Piotr and Murzabulatov, Meiram and Raskhodnikova, Sofya}, title = {{Testing Convexity of Figures Under the Uniform Distribution}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {17:1--17:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-009-5}, ISSN = {1868-8969}, year = {2016}, volume = {51}, editor = {Fekete, S\'{a}ndor and Lubiw, Anna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.17}, URN = {urn:nbn:de:0030-drops-59094}, doi = {10.4230/LIPIcs.SoCG.2016.17}, annote = {Keywords: Convex sets, 2D geometry, randomized algorithms, property testing} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Piotr Berman, Sofya Raskhodnikova, and Ge Ruan. Finding Sparser Directed Spanners. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 424-435, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{berman_et_al:LIPIcs.FSTTCS.2010.424, author = {Berman, Piotr and Raskhodnikova, Sofya and Ruan, Ge}, title = {{Finding Sparser Directed Spanners}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {424--435}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.424}, URN = {urn:nbn:de:0030-drops-28830}, doi = {10.4230/LIPIcs.FSTTCS.2010.424}, annote = {Keywords: Approximation algorithms, directed graphs, spanners} }
Feedback for Dagstuhl Publishing