Authors:
(1) Diptarka Chakraborty, National University of Singapore, Singapore
(2) Sourav Chakraborty, Indian Statistical Institute, Kolkata;
(3) Gunjan Kumar, National University of Singapore, Singapore;
(4) Kuldeep S. Meel, University of Toronto, Toronto.
Table of Links
4 An Efficient One-Round Adaptive Algorithm and 4.1 High-Level Overview
6 Acknowledgements and References
B An O(log log n)-query fully adaptive algorithm
3 Related Work
In the standard SAMP model, the query complexity of the equivalence testing problem is Θ(max(n 2/3/ε4/3 , √ n/ε2 )) [CDVV14, BFR+13, Val11], which is prohibited in most practical applications. The COND model turns out to be beneficial in this context, enabling to require only O˜(log log n) samples [FJO+15], which has recently been shown to be optimal [CCK24].
Unfortunately, the above-mentioned optimal tester in the COND model is sequential. In simpler terms, the tester is adaptive, meaning that each query (indexed as t for any t ≥ 1) in the COND model depends on the answers to the preceding t−1 queries. Designing a parallel, ideally entirely non-adaptive, tester remains an enormous challenge. [KT19] introduced a non-adaptive tester for the equivalence testing problem, which required O˜(log12 n/ε2 ) queries[1] . However, the substantial poly-logarithmic dependency on the domain size is impractical in many real-world applications. Moreover, the best-known lower bound for the query complexity of non-adaptive testers is Ω(log n) [ACK18], indicating considerable room for improvement in the upper bound. One exciting question is to make the tester as less adaptive as possible while attaining the optimal non-adaptive query complexity. Such a question motivates the researchers to study the trade-off between the number of adaptive rounds and the query complexity (for testing various properties). The work [CG18] led to the establishment of a “hierarchy theorem” examining the impact of the number of adaptive rounds.
For the classical equivalence testing problem, in this paper, we make significant strides toward achieving optimal (non-adaptive) query complexity of O(log n) by allowing only one round of adaptivity.
This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license.
[1] Note that O˜(f(n)) notation hides poly(log f(n)) terms.