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.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 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Hadley Black, Iden Kalemaj, and Sofya Raskhodnikova. Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 25:1-25:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{black_et_al:LIPIcs.ICALP.2023.25, author = {Black, Hadley and Kalemaj, Iden and Raskhodnikova, Sofya}, title = {{Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {25:1--25:20}, 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.25}, URN = {urn:nbn:de:0030-drops-180774}, doi = {10.4230/LIPIcs.ICALP.2023.25}, annote = {Keywords: Isoperimetric inequalities, property testing, monotonicity testing} }
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 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma. Sublinear-Time Computation in the Presence of Online Erasures. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 90:1-90:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{kalemaj_et_al:LIPIcs.ITCS.2022.90, author = {Kalemaj, Iden and Raskhodnikova, Sofya and Varma, Nithin}, title = {{Sublinear-Time Computation in the Presence of Online Erasures}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {90:1--90:25}, 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.90}, URN = {urn:nbn:de:0030-drops-156867}, doi = {10.4230/LIPIcs.ITCS.2022.90}, annote = {Keywords: Randomized algorithms, property testing, Fourier analysis, linear functions, quadratic functions, Lipschitz and monotone functions, sorted sequences} }
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 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Sofya Raskhodnikova, Noga Ron-Zewi, and Nithin Varma. Erasures vs. Errors in Local Decoding and Property Testing. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 63:1-63:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{raskhodnikova_et_al:LIPIcs.ITCS.2019.63, author = {Raskhodnikova, Sofya and Ron-Zewi, Noga and Varma, Nithin}, title = {{Erasures vs. Errors in Local Decoding and Property Testing}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {63:1--63:21}, 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.63}, URN = {urn:nbn:de:0030-drops-101568}, doi = {10.4230/LIPIcs.ITCS.2019.63}, annote = {Keywords: Error-correcting codes, probabilistically checkable proofs (PCPs) of proximity, Hadamard code, local list decoding, tolerant testing} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Sofya Raskhodnikova and Nithin Varma. Brief Announcement: Erasure-Resilience Versus Tolerance to Errors. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 111:1-111:3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{raskhodnikova_et_al:LIPIcs.ICALP.2018.111, author = {Raskhodnikova, Sofya and Varma, Nithin}, title = {{Brief Announcement: Erasure-Resilience Versus Tolerance to Errors}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {111:1--111:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.111}, URN = {urn:nbn:de:0030-drops-91154}, doi = {10.4230/LIPIcs.ICALP.2018.111}, annote = {Keywords: Property testing, erasures, tolerance to errors, model separation} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma. Parameterized Property Testing of Functions. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 12:1-12:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{pallavoor_et_al:LIPIcs.ITCS.2017.12, author = {Pallavoor, Ramesh Krishnan S. and Raskhodnikova, Sofya and Varma, Nithin}, title = {{Parameterized Property Testing of Functions}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {12:1--12:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.12}, URN = {urn:nbn:de:0030-drops-81479}, doi = {10.4230/LIPIcs.ITCS.2017.12}, annote = {Keywords: Sublinear algorithms, property testing, parameterization, monotonicity, convexity} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri. Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 5:1-5:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{baleshzar_et_al:LIPIcs.ICALP.2017.5, author = {Baleshzar, Roksana and Chakrabarty, Deeparnab and Pallavoor, Ramesh Krishnan S. and Raskhodnikova, Sofya and Seshadhri, C.}, title = {{Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {5:1--5:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.5}, URN = {urn:nbn:de:0030-drops-74844}, doi = {10.4230/LIPIcs.ICALP.2017.5}, annote = {Keywords: Property testing, unate and monotone functions} }
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.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.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 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin Varma. Erasure-Resilient Property Testing. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 91:1-91:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{dixit_et_al:LIPIcs.ICALP.2016.91, author = {Dixit, Kashyap and Raskhodnikova, Sofya and Thakurta, Abhradeep and Varma, Nithin}, title = {{Erasure-Resilient Property Testing}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {91:1--91:15}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.91}, URN = {urn:nbn:de:0030-drops-61947}, doi = {10.4230/LIPIcs.ICALP.2016.91}, annote = {Keywords: Randomized algorithms, property testing, error correction, monotoneand Lipschitz functions} }
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.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.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