SAMP Model Vs COND Model In Equivalence Testing
by Computational Technology for AllDecember 9th, 2024
Too Long; Didn't Read
The aim is to assess whether the input distribution(s) possess specific properties or deviate significantly (i.e., “ε-far” for some ε 0) from meeting them. The goal is to do this while minimizing the number of queries made (also known as query complexity) to the distribution. The COND model and its variants have recently found applications in the areas like formal methods and machine learning.
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.
L O A D I N G
. . . comments & more!
. . . comments & more!
