Logo

Results in Distribution Testing

Note: the information here is (always) incomplete and updated often
Logo
Maintained by: Uddalok Sarkar, Yash Pote and Sayantan Sen

Closeness Distance :

Farness Distance :

Bound :
Query Complexity of Model vs Model setup
SAMP DUAL PAIRCOND SUBCOND COND
SAMP  
DUAL    
PAIRCOND      
SUBCOND        
COND          
FULL          
 
Notes:
  1. The Total Variation distance \(d_{TV}\) between two probability distributions \(P\) and \(Q\) is defined as: \(d_{TV}(P, Q) = \frac{1}{2} \sum_{x} |P(x) - Q(x)|\)
  2. The Support of a distribution is denoted by \(\Sigma\), and the Support size is denoted by \(N\), so that \(|\Sigma| = N\). For joint distributions on \(d\) dimensions, the Support is denoted by \(\Sigma^d\) and the corresponding Support size is \(N^d\).
  3. The query complexity of a distribution testing problem is the number of queries made by the algorithm to the distribution oracle to distinguish between the null hypothesis and the alternative hypothesis.

References

  1. Testing Closeness of Discrete Distributions [ Paper | ]
    @article{batu2013testing, title={Testing closeness of discrete distributions}, author={Batu, Tu{\u{g}}kan and Fortnow, Lance and Rubinfeld, Ronitt and Smith, Warren D and White, Patrick}, journal={Journal of the ACM (JACM)}, volume={60}, number={1}, pages={1--25}, year={2013}, publisher={ACM New York, NY, USA} }
    Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White
  2. An Automatic Inequality Prover and Instance Optimal Identity Testing [ Paper | ]
    @article{valiant2017automatic, title={An Automatic Inequality Prover and Instance Optimal Identity Testing}, author = {Gregory Valiant and Paul Valiant}, journal={{SIAM} J. Comput.}, volume = {46}, number = {1}, pages = {429--455}, year = {2017} }
    Gregory Valiant, Paul Valiant,
  3. On Distribution Testing in the Conditional Sampling Model [ Paper | ]
    @article{nar2020cond, author = {Shyam Narayanan}, title = {Tolerant Distribution Testing in the Conditional Sampling Model}, journal = {CoRR}, volume = {abs/2007.09895}, year = {2020} }
    Shyam Narayanan
  4. Property Testing of Joint Distributions using Conditional Samples [ Paper | ]
    @article{bhattacharyya2018property, author = {Rishiraj Bhattacharyya and Sourav Chakraborty}, title = {Property Testing of Joint Distributions using Conditional Samples}, journal = {CoRR}, volume = {abs/1702.01454}, year = {2017} }
    Rishiraj Bhattacharyya, Sourav Chakraborty
  5. Testing Bayesian Networks [ Paper | ]
    @inproceedings{canonne2017testing, title={Testing bayesian networks}, author={Canonne, Cl{\'e}ment L and Diakonikolas, Ilias and Kane, Daniel M and Stewart, Alistair}, booktitle={Conference on Learning Theory}, pages={370--448}, year={2017}, organization={PMLR} }
    Clement L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
  6. Testing probability distributions using conditional samples [ Paper | ]
    @article{canonne2015testing, title={Testing probability distributions using conditional samples}, author={Canonne, Cl{\'e}ment L and Ron, Dana} volume={44}, number={3}, pages={540--616}, year={2015}, publisher={SIAM} }
    Clement L. Canonne, Dana Ron, Rocco A. Servedio
  7. On the power of conditional samples in distribution testing [ Paper | ]
    @inproceedings{chakraborty2013power, title={On the power of conditional samples in distribution testing}, author={Chakraborty, Sourav and Fischer, Eldar and Goldhirsh, Yonatan and Matsliah, Arie}, booktitle={Proceedings of the 4th conference on Innovations in Theoretical Computer Science}, pages={561--580}, year={2013} }
    Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah
  8. On Scalable Testing of Samplers [ Paper | ]
    @inproceedings{potescalable, title={On Scalable Testing of Samplers}, author={Pote, Yash and Meel, Kuldeep S}, booktitle={Advances in Neural Information Processing Systems} }
    Yash Pote, Kuldeep S. Meel
  9. Faster Algorithms for Testing under Conditional Sampling [ PMLR | ]
    @inproceedings{falahatgar2015faster, title={Faster algorithms for testing under conditional sampling}, author={Falahatgar, Moein and Jafarpour, Ashkan and Orlitsky, Alon and Pichapati, Venkatadheeraj and Suresh, Ananda Theertha}, booktitle={Conference on Learning Theory}, pages={607--636}, year={2015}, organization={PMLR} }
    Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, Ananda Theertha Suresh
  10. Testing Self-Reducible Samplers [ Paper | ]
    @inproceedings{bhattacharyya2024testing, title={Testing Self-Reducible Samplers}, author={Bhattacharyya, Rishiraj and Chakraborty, Sourav and Pote, Yash and Sarkar, Uddalok and Sen, Sayantan}, booktitle={Proceedings of the AAAI Conference on Artificial Intelligence}, volume={38}, number={8}, pages={7952--7960}, year={2024} }
    Rishiraj Bhattacharyya, Sourav Chakraborty, Yash Pote, Uddalok Sarkar, Sayantan Sen
  11. Tolerant Testing of High-Dimensional Samplers with Subcube Conditioning [ Paper | ]
    @article{kumar2023tolerant, title={Tolerant Testing of High-Dimensional Samplers with Subcube Conditioning}, author={Kumar, Gunjan and Meel, Kuldeep S and Pote, Yash}, journal={arXiv preprint arXiv:2308.04264}, year={2023} }
    Gunjan Kumar, Kuldeep S. Meel, Yash Pote
  12. Testing Symmetric Properties of Distributions [ Paper | ]
    @inproceedings{valiant2008testing, title={Testing symmetric properties of distributions}, author={Valiant, Paul}, booktitle={Proceedings of the fortieth annual ACM symposium on Theory of computing}, pages={383--392}, year={2008} }
    Paul valiant
  13. Testing probability distributions underlying aggregated data [ Paper | ]
    @inproceedings{canonne2014testing, title={Testing probability distributions underlying aggregated data}, author={Canonne, Cl{\'e}ment and Rubinfeld, Ronitt}, booktitle={International Colloquium on Automata, Languages, and Programming}, pages={283--295}, year={2014}, organization={Springer} }
    Clement Canonne, Ronitt Rubinfeld
  14. Minimax Estimation of the L1 Distance [ Paper | ]
    @article{jiao2018minimax, title={Minimax estimation of the $ L\_ $\{$1$\}$ $ distance}, author={Jiao, Jiantao and Han, Yanjun and Weissman, Tsachy}, journal={IEEE Transactions on Information Theory}, volume={64}, number={10}, pages={6672--6706}, year={2018}, publisher={IEEE} }
    Jiantao Jiao, Yanjun Han, Tsachy Weissman
  15. Tight Lower Bound on Equivalence Testing in Conditional Sampling Model [ Paper | ]
    @inproceedings{chakraborty2024tight, title={Tight lower bound on equivalence testing in conditional sampling model}, author={Chakraborty, Diptarka and Chakraborty, Sourav and Kumar, Gunjan}, booktitle={Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)}, pages={4371--4394}, year={2024}, organization={SIAM} }
    Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar