111 reads
EquivTester Samples In Equivalence Testing Algorithm
by Computational Technology for AllDecember 9th, 2024
Too Long; Didn't Read
The article takes an example of an EquivTester algorithm and how to convert it into a one-round algorithm, using the COND model.
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
4.2 Algorithm Description
Our algorithm, EquivTester, takes as input, two distributions P and Q, and a parameter ε > 0. It returns Accept if P = Q and Reject if their total variation distance dT V (P, Q) is greater than ε, both with at least 2/3 probability.
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!
