Equivalence Testing: The Power of Bounded Adaptivity: Acknowledgements and References

Table of Links

Abstract and 1 Introduction

2 Notations and Preliminaries

3 Related Work

4 An Efficient One-Round Adaptive Algorithm and 4.1 High-Level Overview

4.2 Algorithm Description

4.3 Technical Analysis

5 Conclusion

6 Acknowledgements and References

A Missing Proofs

B An O(log log n)-query fully adaptive algorithm

6 Acknowledgements

We thank the anonymous reviewers for their useful comments. D. Chakraborty is supported in part by an MoE AcRF Tier 2 grant (MOE-T2EP20221-0009), an MoE AcRF Tier 1 grant (T1 251RES2303), and a Google South & South-East Asia Research Award. K. S. Meel is supported in part by National Research Foundation Singapore under its NRF Fellowship Programme [NRF-NRFFAI1-2019-0004 ], Ministry of Education Singapore Tier 2 grant MOE-T2EP20121-0011, and Ministry of Education Singapore Tier 1 Grant [R-252-000-B59-114].

References

[AAAK17] Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, and Sanjeev Khanna. Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons. In Conference on Learning Theory, pages 39–75. PMLR, 2017.

[ACK18] Jayadev Acharya, Cl´ement L Canonne, and Gautam Kamath. A chasm between identity and equivalence testing with conditional queries. Theory of Computing, 14(19):1–46, 2018.

[BC18] Rishiraj Bhattacharyya and Sourav Chakraborty. Property testing of joint distributions using conditional samples. ACM Transactions on Computation Theory (TOCT), 10(4):1–20, 2018.

[BFR+13] Tu˘gkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D Smith, and Patrick White. Testing closeness of discrete distributions. Journal of the ACM (JACM), 60(1):1–25, 2013.

[BS18] Eric Balkanski and Yaron Singer. The adaptive complexity of maximizing a submodular function. In Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, pages 1138– 1151, 2018.

[CCK+21] Cl´ement L Canonne, Xi Chen, Gautam Kamath, Amit Levi, and Erik Waingarten. Random restrictions of high dimensional distributions and uniformity testing with subcube conditioning. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2021.

[CCK24] Diptarka Chakraborty, Sourav Chakraborty, and Gunjan Kumar. Tight lower bound on equivalence testing in conditional sampling model. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4371–4394. SIAM, 2024.

[CDVV14] Siu-On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant. Optimal algorithms for testing closeness of discrete distributions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1193–1203. SIAM, 2014.

[CFGM13] Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah. On the power of conditional samples in distribution testing. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 561–580, 2013.

[CG18] Cl´ement L Canonne and Tom Gur. An adaptivity hierarchy theorem for property testing. computational complexity, 27:671–716, 2018.

[CJLW21] Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. Learning and testing junta distributions with sub cube conditioning. In Conference on Learning Theory, pages 1060–1113. PMLR, 2021.

[CKM23] Diptarka Chakraborty, Gunjan Kumar, and Kuldeep S. Meel. Support size estimation: The power of conditioning. In Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 - September 01, 2023, 2023.

[CM19] Sourav Chakraborty and Kuldeep S Meel. On testing of uniform samplers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33-01, pages 7777–7784, 2019.

[CQ19] Chandra Chekuri and Kent Quanrud. Parallelizing greedy for submodular set function maximization in matroids and beyond. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 78–89, 2019.

[CRS14] Cl´ement Canonne, Dana Ron, and Rocco A Servedio. Testing equivalence between distributions using conditional samples. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1174–1192. SIAM, 2014.

[DHH00] Dingzhu Du, Frank K Hwang, and Frank Hwang. Combinatorial group testing and its applications, volume 12. World Scientific, 2000.

[DMT13] Peter Damaschke, Azam Sheikh Muhammad, and Eberhard Triesch. Two new perspectives on multi-stage group testing. Algorithmica, 67:324–354, 2013.

[EBE20] Jens Niklas Eberhardt, Nikolas Peter Breuckmann, and Christiane Sigrid Eberhardt. Multi-stage group testing improves efficiency of large-scale covid-19 screening. Journal of Clinical Virology, 128:104382, 2020. [FJO+15] Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, and Ananda Theertha Suresh. Faster algorithms for testing under conditional sampling. In Conference on Learning Theory, pages 607–636. PMLR, 2015.

[GGR98] Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 45(4):653–750, 1998.

[GJM22] Priyanka Golia, Brendan Juba, and Kuldeep S Meel. A scalable Shannon entropy estimator. In Computer Aided Verification: 34th International Conference, CAV 2022, Haifa, Israel, August 7–10, 2022, Proceedings, Part I, pages 363–384. Springer, 2022.

[GR11] Oded Goldreich and Dana Ron. On testing expansion in bounded-degree graphs. Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation: In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman, pages 68–75, 2011.

[KP19] Akshay Kamath and Eric Price. Adaptive sparse recovery with limited adaptivity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2729–2744. SIAM, 2019.

[KT19] Gautam Kamath and Christos Tzamos. Anaconda: A non-adaptive conditional sampling algorithm for distribution testing. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 679–693. SIAM, 2019.

[MPC20] Kuldeep S Meel, Yash Pralhad Pote, and Sourav Chakraborty. On testing of samplers. Advances in Neural Information Processing Systems, 33:5753–5763, 2020.

[Nar21] Shyam Narayanan. On tolerant distribution testing in the conditional sampling model. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 357– 373. SIAM, 2021.

[NSWZ18] Vasileios Nakos, Xiaofei Shi, David P Woodruff, and Hongyang Zhang. Improved algorithms for adaptive compressed sensing. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.

[Val11] Paul Valiant. Testing symmetric properties of distributions. SIAM Journal on Computing, 40(6):1927–1968, 2011.