Equivalence Testing: An O(log log n)-query Fully Adaptive Algorithm

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 B An O˜(log log n)-query fully adaptive algorithm Our algorithm can also be modified slightly to obtain a fully adaptive algorithm with sample complexity O˜(log log n). This matches the best-known bound in this setting by [FJO+15]. In the original formulation, our algorithm sequentially examines all log n possible values of t to find a particular value, t ∗ . At t ∗ , one of our subroutines—either EstProb or EstTail—will Reject if the input distributions significantly differ. Employing a binary search for t ∗ reduces the number of queries to O˜(log log n). However, this process requires adaptivity at each iteration. This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license. 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 B An O˜(log log n)-query fully adaptive algorithm Our algorithm can also be modified slightly to obtain a fully adaptive algorithm with sample complexity O˜(log log n). This matches the best-known bound in this setting by [FJO+15]. In the original formulation, our algorithm sequentially examines all log n possible values of t to find a particular value, t ∗ . At t ∗ , one of our subroutines—either EstProb or EstTail—will Reject if the input distributions significantly differ. Employing a binary search for t ∗ reduces the number of queries to O˜(log log n). However, this process requires adaptivity at each iteration. 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