New Story
Equivalence Testing: An O(log log n)-query Fully Adaptive Algorithm
by Computational Technology for AllDecember 9th, 2024
Too Long; Didn't Read
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].
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
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.
L O A D I N G
. . . comments & more!
. . . comments & more!
