1 Search Results for "Acharya, Jayadev"

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.449
A Chasm Between Identity and Equivalence Testing with Conditional Queries

Authors: Jayadev Acharya, Clément L. Canonne, and Gautam Kamath

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
A recent model for property testing of probability distributions enables tremendous savings in the sample complexity of testing algorithms, by allowing them to condition the sampling on subsets of the domain. In particular, Canonne, Ron, and Servedio showed that, in this setting, testing identity of an unknown distribution D (i.e., whether D = D* for an explicitly known D*) can be done with a constant number of samples, independent of the support size n - in contrast to the required sqrt(n) in the standard sampling model. However, it was unclear whether the same held for the case of testing equivalence, where both distributions are unknown. Indeed, while Canonne, Ron, and Servedio established a polylog(n)-query upper bound for equivalence testing, very recently brought down to ~O(log(log(n))) by Falahatgar et al., whether a dependence on the domain size n is necessary was still open, and explicitly posed by Fischer at the Bertinoro Workshop on Sublinear Algorithms. In this work, we answer the question in the positive, showing that any testing algorithm for equivalence must make Omega(sqrt(log(log(n)))) queries in the conditional sampling model. Interestingly, this demonstrates an intrinsic qualitative gap between identity and equivalence testing, absent in the standard sampling model (where both problems have sampling complexity n^(Theta(1))). Turning to another question, we investigate the complexity of support size estimation. We provide a doubly-logarithmic upper bound for the adaptive version of this problem, generalizing work of Ron and Tsur to our weaker model. We also establish a logarithmic lower bound for the non-adaptive version of this problem. This latter result carries on to the related problem of non-adaptive uniformity testing, an exponential improvement over previous results that resolves an open question of Chakraborty, Fischer, Goldhirsh, and Matsliah.
Cite as

Jayadev Acharya, Clément L. Canonne, and Gautam Kamath. A Chasm Between Identity and Equivalence Testing with Conditional Queries. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 449-466, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{acharya_et_al:LIPIcs.APPROX-RANDOM.2015.449,
  author =	{Acharya, Jayadev and Canonne, Cl\'{e}ment L. and Kamath, Gautam},
  title =	{{A Chasm Between Identity and Equivalence Testing with Conditional Queries}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{449--466},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.449},
  URN =		{urn:nbn:de:0030-drops-53178},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.449},
  annote =	{Keywords: property testing, probability distributions, conditional samples}
}
  • Refine by Author
  • 1 Acharya, Jayadev
  • 1 Canonne, Clément L.
  • 1 Kamath, Gautam

  • Refine by Classification

  • Refine by Keyword
  • 1 conditional samples
  • 1 probability distributions
  • 1 property testing

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact