A chasm between identity and equivalence testing with conditional queries

DOI10.4086/TOC.2018.V014A019MaRDI QIDQ4612483zbMATH OpenOpenAlexFDO

Authors Jayadev Acharya, Clement L. Canonne, Gautam Kamath

Publication date 31 January 2019

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2018.v014a019

zbMATH Keywords

conditional samplingdistribution testingequivalence testinglower boundsproperty testingsupport size estimationuniformity testing

Mathematics Subject Classification ID

Combinatorial probability (60C05) Inequalities; stochastic orderings (60E15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• A Chasm Between Identity and Equivalence Testing with Conditional Queries
• Testing equivalence between distributions using conditional samples
• \textsc{Anaconda}: a non-adaptive conditional sampling algorithm for distribution testing
• Testing probability distributions using conditional samples

Cites work

• A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete Data
• Algorithmic and analysis techniques in property testing
• An automatic inequality prover and instance optimal identity testing
• Balls and bins: A study in negative dependence
• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 1508646 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 5686753 (Why is no real title available?)
• Non-Adaptive Group Testing: Explicit Bounds and Novel Algorithms
• On Approximation Algorithms for # P
• Optimal algorithms for testing closeness of discrete distributions
• Property testing. Current research and surveys
• Sublinear algorithms for testing monotone and unimodal distributions
• Sublinear estimation of entropy and information distances
• Testing monotone high‐dimensional distributions
• Testing probability distributions underlying aggregated data
• Testing probability distributions using conditional samples
• Testing properties of collections of distributions
• Testing Symmetric Properties of Distributions
• The power of an example: hidden set size approximation using group queries and conditional sampling
• The Power of Linear Estimators
• The tail of the hypergeometric distribution

Cited in

(6)

• \textsc{Anaconda}: a non-adaptive conditional sampling algorithm for distribution testing
• Testing probability distributions using conditional samples
• A Chasm Between Identity and Equivalence Testing with Conditional Queries
• Testing equivalence between distributions using conditional samples
• On tolerant distribution testing in the conditional sampling model
• A scalable entropy estimator

This page was built for publication: A chasm between identity and equivalence testing with conditional queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4612483)