@COMMENT This file was generated by bib2html.pl <https://sourceforge.net/projects/bib2html/> version 0.94
@COMMENT written by Patrick Riley <http://sourceforge.net/users/patstg/>
@COMMENT This file came from Kuldeep S. Meel's publication pages at
@COMMENT http://www.comp.nus.edu.sg/~meel/publications/
@inproceedings{CCKM24,
  author={
    Chakraborty, Diptarka and Chakraborty, Sourav and Kumar, Gunjan and Meel,
    Kuldeep S.
  },
  title={Equivalence Testing: The Power of Bounded Adaptivity},
  abstract={
    Equivalence testing, a fundamental problem
    in the field of distribution testing,
    seeks to infer if two unknown distributions
    on $[n]$ are the same or far apart in the
    total variation distance. Conditional
    sampling has emerged as a powerful query
    model and has been investigated by
    theoreticians and practitioners alike,
    leading to the design of optimal algorithms
    albeit in a sequential setting (also
    referred to as adaptive tester).
    Given the profound impact of parallel
    computing over the past decades, there has been a
    strong desire to design algorithms that
    enable high parallelization. Despite
    significant algorithmic advancements over
    the last decade, parallelizable techniques
    (also termed non-adaptive testers) have
    $\Tilde{O}(\log^{12}n)$ query complexity, a
    prohibitively large complexity to be of
    practical usage.
    Therefore, the primary challenge is whether
    it is possible to design algorithms that
    enable high parallelization while achieving
    efficient query complexity.
    Our work provides an affirmative answer to
    the aforementioned challenge: we present a
    highly parallelizable tester with a query
    complexity of $\Tilde{O}(\log n)$, achieved
    through a single round of adaptivity,
    marking a significant stride towards
    harmonizing parallelizability and
    efficiency in equivalence testing.
  },
  year={2024},
  month=apr,
  booktitle=AISTATS,
  bib2html_pubtype={Refereed Conference},
  bib2html_rescat={Distribution Testing},
  bib2html_dl_pdf={https://arxiv.org/abs/2403.04230.pdf},
}