Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Clément L. Canonne and Yucheng Sun. Private Distribution Testing with Heterogeneous Constraints: Your Epsilon Might Not Be Mine. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 23:1-23:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{canonne_et_al:LIPIcs.ITCS.2024.23, author = {Canonne, Cl\'{e}ment L. and Sun, Yucheng}, title = {{Private Distribution Testing with Heterogeneous Constraints: Your Epsilon Might Not Be Mine}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {23:1--23:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.23}, URN = {urn:nbn:de:0030-drops-195518}, doi = {10.4230/LIPIcs.ITCS.2024.23}, annote = {Keywords: differential privacy, distribution testing, local privacy, shuffle privacy} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Ilan Newman and Nithin Varma. Strongly Sublinear Algorithms for Testing Pattern Freeness. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 98:1-98:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{newman_et_al:LIPIcs.ICALP.2022.98, author = {Newman, Ilan and Varma, Nithin}, title = {{Strongly Sublinear Algorithms for Testing Pattern Freeness}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {98:1--98: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.98}, URN = {urn:nbn:de:0030-drops-164390}, doi = {10.4230/LIPIcs.ICALP.2022.98}, annote = {Keywords: Property testing, Pattern freeness, Sublinear algorithms} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Clément L. Canonne and Karl Wimmer. Identity Testing Under Label Mismatch. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 55:1-55:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{canonne_et_al:LIPIcs.ISAAC.2021.55, author = {Canonne, Cl\'{e}ment L. and Wimmer, Karl}, title = {{Identity Testing Under Label Mismatch}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {55:1--55:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.55}, URN = {urn:nbn:de:0030-drops-154880}, doi = {10.4230/LIPIcs.ISAAC.2021.55}, annote = {Keywords: distribution testing, property testing, permutations, lower bounds} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Clément L. Canonne and Karl Wimmer. Testing Data Binnings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{canonne_et_al:LIPIcs.APPROX/RANDOM.2020.24, author = {Canonne, Cl\'{e}ment L. and Wimmer, Karl}, title = {{Testing Data Binnings}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {24:1--24:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.24}, URN = {urn:nbn:de:0030-drops-126277}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.24}, annote = {Keywords: property testing, distribution testing, identity testing, hypothesis testing} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Bruce Spang and Mary Wootters. Unconstraining Graph-Constrained Group Testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{spang_et_al:LIPIcs.APPROX-RANDOM.2019.46, author = {Spang, Bruce and Wootters, Mary}, title = {{Unconstraining Graph-Constrained Group Testing}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {46:1--46:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.46}, URN = {urn:nbn:de:0030-drops-112615}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.46}, annote = {Keywords: Group testing, network tomography, random graphs} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, and Karl Wimmer. Testing k-Monotonicity. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 29:1-29:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{canonne_et_al:LIPIcs.ITCS.2017.29, author = {Canonne, Cl\'{e}ment L. and Grigorescu, Elena and Guo, Siyao and Kumar, Akash and Wimmer, Karl}, title = {{Testing k-Monotonicity}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {29:1--29:21}, 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.29}, URN = {urn:nbn:de:0030-drops-81583}, doi = {10.4230/LIPIcs.ITCS.2017.29}, annote = {Keywords: Boolean Functions, Learning, Monotonicity, Property Testing} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Clément L. Canonne and Tom Gur. An Adaptivity Hierarchy Theorem for Property Testing. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 27:1-27:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{canonne_et_al:LIPIcs.CCC.2017.27, author = {Canonne, Cl\'{e}ment L. and Gur, Tom}, title = {{An Adaptivity Hierarchy Theorem for Property Testing}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {27:1--27:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.27}, URN = {urn:nbn:de:0030-drops-75164}, doi = {10.4230/LIPIcs.CCC.2017.27}, annote = {Keywords: Property Testing, Coding Theory, Hierarchy Theorems} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Eric Blais, Clément L. Canonne, and Tom Gur. Distribution Testing Lower Bounds via Reductions from Communication Complexity. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 28:1-28:40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{blais_et_al:LIPIcs.CCC.2017.28, author = {Blais, Eric and Canonne, Cl\'{e}ment L. and Gur, Tom}, title = {{Distribution Testing Lower Bounds via Reductions from Communication Complexity}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {28:1--28:40}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.28}, URN = {urn:nbn:de:0030-drops-75366}, doi = {10.4230/LIPIcs.CCC.2017.28}, annote = {Keywords: Distribution testing, communication complexity, lower bounds, simultaneous message passing, functional analysis} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis, and Ronitt Rubinfeld. Testing Shape Restrictions of Discrete Distributions. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{canonne_et_al:LIPIcs.STACS.2016.25, author = {Canonne, Cl\'{e}ment L. and Diakonikolas, Ilias and Gouleakis, Themis and Rubinfeld, Ronitt}, title = {{Testing Shape Restrictions of Discrete Distributions}}, booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)}, pages = {25:1--25:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-001-9}, ISSN = {1868-8969}, year = {2016}, volume = {47}, editor = {Ollinger, Nicolas and Vollmer, Heribert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.25}, URN = {urn:nbn:de:0030-drops-57260}, doi = {10.4230/LIPIcs.STACS.2016.25}, annote = {Keywords: property testing, probability distributions, statistics, lower bounds} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Jayadev Acharya, Clément L. Canonne, and Gautam Kamath. A Chasm Between Identity and Equivalence Testing with Conditional Queries. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 449-466, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{acharya_et_al:LIPIcs.APPROX-RANDOM.2015.449, author = {Acharya, Jayadev and Canonne, Cl\'{e}ment L. and Kamath, Gautam}, title = {{A Chasm Between Identity and Equivalence Testing with Conditional Queries}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {449--466}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.449}, URN = {urn:nbn:de:0030-drops-53178}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.449}, annote = {Keywords: property testing, probability distributions, conditional samples} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Eric Blais, Clément L. Canonne, Igor C. Oliveira, Rocco A. Servedio, and Li-Yang Tan. Learning Circuits with few Negations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 512-527, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{blais_et_al:LIPIcs.APPROX-RANDOM.2015.512, author = {Blais, Eric and Canonne, Cl\'{e}ment L. and Oliveira, Igor C. and Servedio, Rocco A. and Tan, Li-Yang}, title = {{Learning Circuits with few Negations}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {512--527}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.512}, URN = {urn:nbn:de:0030-drops-53214}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.512}, annote = {Keywords: Boolean functions, monotonicity, negations, PAC learning} }
Feedback for Dagstuhl Publishing