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 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 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. 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. Authors: 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 Abstract and 1 Introduction Abstract and 1 Introduction 2 Notations and Preliminaries 2 Notations and Preliminaries 3 Related Work 3 Related Work 4 An Efficient One-Round Adaptive Algorithm and 4.1 High-Level Overview 4 An Efficient One-Round Adaptive Algorithm and 4.1 High-Level Overview 4.2 Algorithm Description 4.2 Algorithm Description 4.3 Technical Analysis 4.3 Technical Analysis 5 Conclusion 5 Conclusion 6 Acknowledgements and References 6 Acknowledgements and References A Missing Proofs A Missing Proofs B An O(log log n)-query fully adaptive algorithm 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. This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license. available on arxiv [1] Note that O˜(f(n)) notation hides poly(log f(n)) terms.

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

An Efficient One-Round Adaptive Algorithm In Equivalence Testing

Understand The Distributions Used In Equivalence Testing

Computational.TECH

Too Long; Didn't Read

Boost your HackerNoon story @ $159.99! 🚀

SAMP Model Vs COND Model In Equivalence Testing

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

A Data-centric Approach to Class-specific Bias in Image Data Augmentation: Abstract and Intro

Explore The Power of Bounded Adaptivity Through Equivalence Testing

Understand The Distributions Used In Equivalence Testing

EquivTester Samples In Equivalence Testing Algorithm

Technical Analysis Of The Correctness And Complexity Of EquivTester

A Data-centric Approach to Class-specific Bias in Image Data Augmentation: Abstract and Intro

Explore The Power of Bounded Adaptivity Through Equivalence Testing

Understand The Distributions Used In Equivalence Testing

EquivTester Samples In Equivalence Testing Algorithm

Technical Analysis Of The Correctness And Complexity Of EquivTester

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps