@inproceedings{ABR:16, author = {Maryam Aliakbarpour and Eric Blais and Ronitt Rubinfeld}, title = {Learning and Testing Junta Distributions}, booktitle = {Proceedings of COLT}, series = {{JMLR} Workshop and Conference Proceedings}, volume = {49}, pages = {19--46}, publisher = {JMLR.org}, year = {2016} }
@inproceedings{DK:16, author = {{Diakonikolas}, Ilias and {Kane}, Daniel~M.}, title = {A New Approach for Testing Properties of Discrete Distributions}, booktitle = {Proceedings of FOCS}, publisher = {{IEEE} Computer Society}, year = {2016} }
@article{Gol:16, author = {Oded Goldreich}, title = {The uniform distribution is complete with respect to testing identity to a fixed distribution}, journal = {Electronic Colloquium on Computational Complexity (ECCC)}, volume = {23}, pages = {15}, year = {2016} }
@article{BBM:12, author = {Blais, Eric and Brody, Joshua and Matulef, Kevin}, title = {Property Testing Lower Bounds via Communication Complexity}, journal = {Computational Complexity}, volume = {21}, number = {2}, pages = {311--358}, year = {2012}, url = {http://dx.doi.org/10.1007/s00037-012-0040-x}, doi = {10.1007/s00037-012-0040-x} }
@article{Goldreich:13, author = {Goldreich, Oded}, title = {{On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing}}, journal = {Electronic Colloquium on Computational Complexity (ECCC)}, volume = {20}, pages = {73}, year = {2013}, ee = {http://eccc.hpi-web.de/report/2013/073} }
@article{BCG:16, author = {Eric Blais and Cl{\'{e}}ment Louis Canonne and Tom Gur}, title = {{Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.)}}, journal = {Electronic Colloquium on Computational Complexity (ECCC)}, volume = {23}, pages = {168}, year = {2016} }
@article{DGPP:16, author = {Ilias Diakonikolas and Themis Gouleakis and John Peebles and Eric Price}, title = {{Collision-based Testers are Optimal for Uniformity and Closeness}}, journal = {ArXiV}, volume = {abs/1611.03579}, year = {2016} }
@article{Ma:81:Physics, year = {1981}, issn = {0022-4715}, journal = {Journal of Statistical Physics}, volume = {26}, number = {2}, doi = {10.1007/BF01013169}, title = {Calculation of entropy from data of motion}, url = {http://dx.doi.org/10.1007/BF01013169}, publisher = {Kluwer Academic Publishers-Plenum Publishers}, author = {Ma, Shang-{K}eng}, pages = {221-240} }
@article{Walther:09, author = {Walther, Guenther}, doi = {10.1214/09-STS303}, journal = {Statistical Science}, month = {08}, number = {3}, pages = {319--327}, publisher = {The Institute of Mathematical Statistics}, title = {Inference and Modeling with Log-concave Distributions}, url = {http://dx.doi.org/10.1214/09-STS303}, volume = {24}, year = {2009} }
@article{Reboul:05, author = {Reboul, Laurence}, journal = {The Annals of Mathematical Statistics}, month = {06}, number = {3}, pages = {1330--1356}, publisher = {The Institute of Mathematical Statistics}, title = {Estimation of a function under shape restrictions. Applications to reliability}, url = {http://dx.doi.org/10.1214/009053605000000138}, volume = {33}, year = {2005} }
@article{Rubinfeld:12:Taming, author = {Rubinfeld, Ronitt}, title = {Taming {B}ig {P}robability {D}istributions}, journal = {XRDS}, issue_date = {Fall 2012}, volume = {19}, number = {1}, month = sep, year = {2012}, issn = {1528-4972}, pages = {24--28}, numpages = {5}, url = {http://doi.acm.org/10.1145/2331042.2331052}, doi = {10.1145/2331042.2331052}, acmid = {2331052}, publisher = {ACM}, address = {New York, NY, USA} }
@misc{Rubinfeld:12:Taming:fr:Canonne, title = {Dompter les {D}istributions de {P}robabilité {G}\'eantes}, howpublished = {\url{http://www.cs.columbia.edu/~ccanonne/files/misc/tamingbigdistr-fr.pdf}}, note = {French translation of~\cite{Rubinfeld:12:Taming}}, author = {Canonne, Cl\'ement L.}, year = 2013 }
@incollection{GV:11:survey, author = {Goldreich, Oded and Vadhan, Salil P.}, editor = {Oded Goldreich}, title = {On the Complexity of Computational Problems Regarding Distributions}, booktitle = {Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation}, series = {Lecture Notes in Computer Science}, volume = {6650}, pages = {390--405}, publisher = {Springer}, year = {2011}, url = {http://dx.doi.org/10.1007/978-3-642-22670-0_27} }
@article{GGR:98, author = {Goldreich, Oded and Goldwasser, Shafi and Ron, Dana}, title = {Property Testing and Its Connection to Learning and Approximation}, journal = {Journal of the ACM}, volume = {45}, number = {4}, month = jul, year = {1998}, pages = {653--750}, publisher = {ACM}, address = {New York, NY, USA} }
@article{Survey:Fischer, author = {Fischer, Eldar}, title = {The art of uninformed decisions: A primer to property testing}, journal = {Bulletin of the European Association for Theoretical Computer Science}, volume = {75}, pages = {97--126}, year = {2001} }
@article{Survey:Ron:08, title = {{Property Testing: A Learning Theory Perspective}}, journal = {Foundations and Trends in Machine Learning}, volume = {1}, number = {3}, pages = {307-402}, year = {2008}, author = {Ron, Dana} }
@article{Survey:Ron:10, title = {Algorithmic and Analysis Techniques in Property Testing}, journal = {Foundations and Trends in Theoretical Computer Science}, volume = 5, issue = 2, year = 2010, pages = {73--205}, author = {Ron, Dana} }
@book{Survey:Goldreich:10, title = {Property Testing: Current Research and Surveys}, year = 2010, publisher = {Springer}, editor = {Goldreich, Oded}, note = {LNCS 6390} }
@article{RS:96, author = {Rubinfeld, Ronitt and Sudan, Madhu}, title = {Robust Characterization of Polynomials with Applications to Program Testing}, journal = {SIAM Journal on Computing}, volume = 25, number = 2, pages = {252--271}, year = 1996 }
@article{BLR:93, author = {Blum, Manuel and Luby, Michael and Rubinfeld, Ronitt}, title = {Self-testing/correcting with applications to numerical problems}, journal = {Journal of Computer and System Sciences}, volume = {47}, pages = {549-595}, year = {1993}, note = {An earlier version of this work appeared in STOC'90} }
@article{Scheffe:47, author = {Scheff\'e, Henry}, doi = {10.1214/aoms/1177730390}, journal = {The Annals of Mathematical Statistics}, month = {09}, number = {3}, pages = {434--438}, publisher = {The Institute of Mathematical Statistics}, title = {A Useful Convergence Theorem for Probability Distributions}, url = {http://dx.doi.org/10.1214/aoms/1177730390}, volume = {18}, year = {1947} }
@article{Glynn:87, author = {Glynn, Peter W.}, title = {Upper Bounds on {P}oisson Tail Probabilities}, journal = {Operations Research Letters}, volume = {6}, number = {1}, month = mar, year = {1987}, issn = {0167-6377}, pages = {9--14}, numpages = {6}, url = {http://dx.doi.org/10.1016/0167-6377(87)90003-4}, doi = {10.1016/0167-6377(87)90003-4}, acmid = {2309926}, publisher = {Elsevier Science Publishers B. V.}, address = {Amsterdam, The Netherlands, The Netherlands} }
@article{SV:03, author = {Sahai, Amit and Vadhan, Salil}, title = {A Complete Problem for {S}tatistical {Z}ero {K}nowledge}, journal = {Journal of the ACM}, volume = {50}, number = {2}, month = mar, year = {2003}, issn = {0004-5411}, pages = {196--249}, numpages = {54}, url = {http://doi.acm.org/10.1145/636865.636868}, doi = {10.1145/636865.636868}, acmid = {636868}, publisher = {ACM}, address = {New York, NY, USA} }
@misc{Pollard:2003, author = {Pollard, David}, title = {Asymptopia}, howpublished = {\url{http://www.stat.yale.edu/~pollard/Books/Asymptopia}}, note = {Manuscript}, year = 2003 }
@misc{HarPeled:CS:Overflow:15, title = {Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$}, author = {Sariel {Har-Peled}}, howpublished = {Theoretical Computer Science Stack Exchange}, note = {\url{http://cstheory.stackexchange.com/q/28024} (version: 2015-01-01)}, url = {http://cstheory.stackexchange.com/q/28024}, year = {2015}, month = jan, day = {1} }
@phdthesis{BarYossef:02, author = {Bar-Yossef, Ziv}, title = {The Complexity of Massive Data Set Computations}, school = {UC Berkeley}, year = {2002}, note = {Adviser: Christos Papadimitriou. Available at~\url{http://webee.technion.ac.il/people/zivby/index_files/Page1489.html}.} }
@phdthesis{Valiant:12, author = {Valiant, Gregory}, title = {Algorithmic Approaches to Statistical Questions}, school = {UC Berkeley}, year = {2012}, note = {Adviser: Christos Papadimitriou} }
@article{KR:58, author = {Kantorovich, Leonid and Rubinstein, Gennady S.}, title = {On a space of totally additive functions}, journal = {Vestnik Leningrad. Univ}, pages = {52--59}, volume = {13}, year = {1958} }
@article{DengDu:09, title = {The {K}antorovich Metric in Computer Science: A Brief Survey}, journal = {Electronic Notes in Theoretical Computer Science}, volume = {253}, number = {3}, pages = {73 -- 82}, year = {2009}, note = {Proceedings of Seventh Workshop on Quantitative Aspects of Programming Languages (QAPL 2009) }, issn = {1571-0661}, doi = {http://dx.doi.org/10.1016/j.entcs.2009.10.006}, url = {http://www.sciencedirect.com/science/article/pii/S1571066109004265}, author = {Deng, Yuxin and Du, Wenjie} }
@article{GibbsSu:02, author = {Gibbs, Alison L. and Su, Francis E.}, title = {On Choosing and Bounding Probability Metrics}, journal = {Interdisciplinary Science Reviews}, eprint = {math/0209021}, year = 2002, month = dec, volume = 70, pages = {419-435}, doi = {10.1111/j.1751-5823.2002.tb00178.x} }
@article{DKW:56, author = {Dvoretzky, Aryeh and Kiefer, Jack and Wolfowitz, Jacob}, doi = {10.1214/aoms/1177728174}, journal = {The Annals of Mathematical Statistics}, month = {09}, number = {3}, pages = {642--669}, publisher = {The Institute of Mathematical Statistics}, title = {Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator}, url = {http://dx.doi.org/10.1214/aoms/1177728174}, volume = {27}, year = {1956} }
@article{Massart:90, author = {Massart, Pascal}, doi = {10.1214/aop/1176990746}, journal = {The Annals of Probability}, month = {07}, number = {3}, pages = {1269--1283}, publisher = {The Institute of Mathematical Statistics}, title = {The Tight Constant in the {D}voretzky--{K}iefer--{W}olfowitz Inequality}, url = {http://dx.doi.org/10.1214/aop/1176990746}, volume = {18}, year = {1990} }
@article{AdellJodra:06, author = {Adell, Jos\'e A. and Jodra, Pedro}, journal = {Journal of Inequalities and Applications}, number = {1}, pages = {64307}, title = {Exact {K}olmogorov and total variation distances between some familiar discrete distributions}, volume = {2006}, year = {2006}, doi = {10.1155/JIA/2006/64307}, issn = {1029-242X} }
@inbook{SW:Poissonization, chapter = {{A}nalytic {P}oissonization and {D}epoissonization}, author = {Szpankowski, Wojciech}, publisher = {John Wiley \& Sons, Inc.}, isbn = {9781118032770}, url = {http://dx.doi.org/10.1002/9781118032770.ch10}, doi = {10.1002/9781118032770.ch10}, pages = {442--519}, title = {Average Case Analysis of Algorithms on Sequences}, year = {2001} }
@article{LeCam:60, ajournal = {Pacific J. Math.}, author = {Le Cam, Lucien}, journal = {Pacific Journal of Mathematics}, number = {4}, pages = {1181--1197}, publisher = {Pacific Journal of Mathematics, A Non-profit Corporation}, title = {An approximation theorem for the {P}oisson binomial distribution}, url = {http://projecteuclid.org/euclid.pjm/1103038058}, volume = {10}, year = {1960} }
@article{PRR:06, author = {Parnas, Michal and Ron, Dana and Rubinfeld, Ronitt}, title = {Tolerant property testing and distance approximation}, journal = {Journal of Computer and System Sciences}, volume = {72}, number = {6}, year = {2006}, pages = {1012-1042}, ee = {http://dx.doi.org/10.1016/j.jcss.2006.03.002}, bibsource = {DBLP, http://dblp.uni-trier.de} }
@misc{Rey:11, author = {Reyzin, Leo}, title = {{Extractors and the leftover hash lemma}}, note = {Lecture notes}, howpublished = {\url{http://www.cs.bu.edu/~reyzin/teaching/s11cs937/notes-leo-1.pdf}}, year = 2011, month = mar }
@article{BaNNR:11, author = {Do Ba, Khanh and Nguyen,Huy L. and Nguyen, Huy N. and Rubinfeld, Ronitt}, title = {Sublinear Time Algorithms for {E}arth {M}over's Distance}, journal = {Theory of Computing Systems}, volume = {48}, number = {2}, year = {2011}, pages = {428-442}, ee = {http://dx.doi.org/10.1007/s00224-010-9265-8}, bibsource = {DBLP, http://dblp.uni-trier.de} }
@article{GRexp:00, author = {Goldreich, Oded and Ron, Dana}, title = {On Testing Expansion in Bounded-Degree Graphs}, journal = {Electronic Colloquium on Computational Complexity (ECCC)}, year = {2000}, pages = {20}, volume = {7}, ee = {http://eccc.hpi-web.de/report/2000/020} }
@inproceedings{BFRSW:00, author = {Batu, Tu\u{g}kan and Fortnow, Lance and Rubinfeld, Ronitt and Smith, Warren D. and White, Patrick}, title = {Testing that distributions are close}, booktitle = {Proceedings of FOCS}, year = {2000}, pages = {189--197} }
@article{BFRSW:10, author = {Batu, Tu\u{g}kan and Fortnow, Lance and Rubinfeld, Ronitt and Smith, Warren D. and White, Patrick}, title = {Testing Closeness of Discrete Distributions}, year = {2013}, journal = {Journal of the ACM}, volume = {60}, number = {1}, pages = {4:1--4:25}, month = feb, publisher = {ACM}, address = {New York, NY, USA}, note = {This is the journal version of~\cite{BFRSW:00}.} }
@article{Paninski:08, author = {Paninski, Liam}, title = {A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete Data}, journal = {IEEE Transactions on Information Theory}, volume = {54}, number = {10}, year = {2008}, pages = {4750-4755}, ee = {http://dx.doi.org/10.1109/TIT.2008.928987} }
@inproceedings{BRY:14, author = {Berman, Piotr and Raskhodnikova, Sofya and Yaroslavtsev, Grigory}, title = {${L}_p$-testing}, booktitle = {Proceedings of STOC}, year = {2014}, isbn = {978-1-4503-2710-7}, location = {New York, New York}, pages = {164--173}, numpages = {10}, url = {http://doi.acm.org/10.1145/2591796.2591887}, doi = {10.1145/2591796.2591887}, acmid = {2591887}, publisher = {ACM}, address = {New York, NY, USA} }
@article{RS:09, address = {New York, NY, USA}, author = {Rubinfeld, Ronitt and Servedio, Rocco A.}, journal = {Random Structures and Algorithms}, month = jan, number = {1}, pages = {24--44}, publisher = {John Wiley \& Sons, Inc.}, title = {Testing monotone high-dimensional distributions}, volume = {34}, year = {2009}, doi = {10.1002/rsa.v34:1}, issn = {1042-9832} }
@inproceedings{CKOCS:15, author = {Caferov, Cafer and Kaya, Bari\c{s} and O'Donnell, Ryan and Say, A. C. Cem}, title = {Optimal Bounds for Estimating Entropy with {PMF} Queries}, booktitle = {{MFCS} {(2)}}, series = {Lecture Notes in Computer Science}, volume = {9235}, pages = {187--198}, publisher = {Springer}, year = {2015} }
@inproceedings{CR:14, author = {Canonne, Cl\'ement L. and Rubinfeld, Ronitt}, title = {Testing Probability Distributions Underlying Aggregated Data}, booktitle = {Proceedings of ICALP}, year = {2014}, pages = {283-295}, ee = {http://dx.doi.org/10.1007/978-3-662-43948-7_24} }
@article{BDKR:05, author = {Batu, Tu\u{g}kan and Dasgupta, Sanjoy and Kumar, Ravi and Rubinfeld, Ronitt}, journal = {SIAM Journal on Computing}, number = {1}, pages = {132--150}, publisher = {Society for Industrial and Applied Mathematics (SIAM)}, title = {The complexity of approximating the entropy}, volume = {35}, year = {2005} }
@inproceedings{GMV:06, author = {Guha, Sudipto and McGregor, Andrew and Venkatasubramanian, Suresh}, title = {Streaming and Sublinear Approximation of Entropy and Information Distances}, booktitle = {Proceedings of SODA}, year = {2006}, isbn = {0-89871-605-5}, location = {Miami, Florida}, pages = {733--742}, numpages = {10}, url = {http://dl.acm.org/citation.cfm?id=1109557.1109637}, acmid = {1109637}, publisher = {Society for Industrial and Applied Mathematics (SIAM)}, address = {Philadelphia, PA, USA} }
@inproceedings{CFGM:13, author = {Chakraborty, Sourav and Fischer, Eldar and Goldhirsh, Yonatan and Matsliah, Arie}, title = {On the Power of Conditional Samples in Distribution Testing}, booktitle = {Proceedings of ITCS}, year = {2013}, isbn = {978-1-4503-1859-4}, location = {Berkeley, California, USA}, pages = {561--580}, numpages = {20}, url = {http://doi.acm.org/10.1145/2422436.2422497}, doi = {10.1145/2422436.2422497}, acmid = {2422497}, publisher = {ACM}, address = {New York, NY, USA} }
@article{CRS:12, author = {Canonne, Cl\'ement L. and Ron, Dana and Servedio, Rocco A.}, journal = {SIAM Journal on Computing}, publisher = {Society for Industrial and Applied Mathematics (SIAM)}, title = {Testing probability distributions using conditional samples}, volume = {44}, number = {3}, pages = {540-616}, year = {2015}, doi = {10.1137/130945508}, note = {Also available on arXiv at \href{http://arxiv.org/abs/1211.2664}{abs/1211.2664}} }
@article{ACK:14, author = {Acharya, Jayadev and Canonne, Cl\'ement L. and Kamath, Gautam}, journal = {ArXiV}, volume = {abs/1411.7346}, title = {A Chasm Between Identity and Equivalence Testing with Conditional Queries}, year = {2014}, month = nov }
@inproceedings{CRS:14, author = {Canonne, Cl\'ement L. and Ron, Dana and Servedio, Rocco A.}, booktitle = {Proceedings of SODA}, title = {Testing equivalence between distributions using conditional samples}, year = {2014}, note = {See also \cite{CRS:12} (full version)}, isbn = {978-1-611973-38-9}, location = {Portland, Oregon}, pages = {1174--1192}, numpages = {19}, url = {http://dl.acm.org/citation.cfm?id=2634074.2634161}, acmid = {2634161}, publisher = {Society for Industrial and Applied Mathematics (SIAM)} }
@inproceedings{FJOPS:15, author = {Falahatgar, Moein and Jafarpour, Ashkan and Orlitsky, Alon and Pichapathi, Venkatadheeraj and Suresh, Ananda Theertha}, title = {Faster Algorithms for Testing under Conditional Sampling}, booktitle = {Proceedings of COLT}, year = {2015}, series = {{JMLR} Proceedings}, pages = {607--636} }
@inproceedings{CRRS:14, author = {Cl{\'{e}}ment L. Canonne}, title = {{B}ig {D}ata on the Rise? {T}esting Monotonicity of Distributions}, booktitle = {Proceedings of ICALP}, series = {Lecture Notes in Computer Science}, volume = {9134}, pages = {294--305}, publisher = {Springer}, year = {2015}, url = {http://dx.doi.org/10.1007/978-3-662-47672-7_24}, doi = {10.1007/978-3-662-47672-7_24}, note = {Also available on arXiv at \href{http://arxiv.org/abs/1501.06783}{abs/1501.06783}.} }
@misc{CRS:13:Monotone, author = {Canonne, Cl\'ement L. and Ron, Dana and Servedio, Rocco A.}, year = {2013}, howpublished = {Private communication} }
@article{LRR:13, author = {Levi, Reut and Ron, Dana and Rubinfeld, Ronitt}, title = {Testing Properties of Collections of Distributions}, journal = {Theory of Computing}, volume = {9}, pages = {295--347}, year = {2013}, url = {http://dx.doi.org/10.4086/toc.2013.v009a008}, doi = {10.4086/toc.2013.v009a008} }
@article{LRR:14, author = {Levi, Reut and Ron, Dana and Rubinfeld, Ronitt}, title = {Testing Similar Means}, journal = {SIAM Journal on Discrete Math}, volume = {28}, number = {4}, pages = {1699--1724}, year = {2014}, url = {http://dx.doi.org/10.1137/120903737}, doi = {10.1137/120903737} }
@article{RRSS:09, author = {Raskhodnikova, Sofya and Ron, Dana and Shpilka, Amir and Smith, Adam}, title = {Strong lower bounds for approximating distributions support size and the distinct elements problem}, journal = {SIAM Journal on Computing}, year = 2009, pages = {813--842}, volume = 39, number = 3 }
@article{Paninski:04, title = {Estimating entropy on $m$ bins given fewer than $m$ samples}, author = {Paninski, Liam}, journal = {IEEE Transactions on Information Theory}, pages = {2200--2203}, volume = {50}, number = {9}, year = {2004} }
@inproceedings{AOST:15, author = {Acharya, Jayadev and Orlitsky, Alon and Suresh, Ananda Theertha and Tyagi, Himanshu}, title = {The Complexity of Estimating {R}{\'{e}}nyi Entropy}, booktitle = {Proceedings of SODA}, pages = {1855--1869}, publisher = {Society for Industrial and Applied Mathematics (SIAM)}, year = {2015} }
@article{ValiantValiant:10lb, author = {Valiant, Gregory and Valiant, Paul}, title = {A {CLT} and tight lower bounds for estimating entropy}, journal = {Electronic Colloquium on Computational Complexity (ECCC)}, volume = {17}, year = {2010}, pages = {179}, ee = {http://eccc.hpi-web.de/report/2010/179} }
@article{ValiantValiant:10ub, author = {Valiant, Gregory and Valiant, Paul}, title = {Estimating the unseen: A sublinear-sample canonical estimator of distributions}, journal = {Electronic Colloquium on Computational Complexity (ECCC)}, volume = {17}, year = {2010}, pages = {180}, ee = {http://eccc.hpi-web.de/report/2010/180} }
@article{WY:14, author = {Wu, Yihong and Yang, Pengkun}, journal = {IEEE Transactions on Information Theory}, title = {Minimax Rates of Entropy Estimation on Large Alphabets via Best Polynomial Approximation}, year = {2016}, volume = {62}, number = {6}, pages = {3702-3720} }
@article{JVW:14, author = {Jiao, Jiantao and Venkat, Kartik and Weissman, Tsachy}, title = {Order-Optimal Estimation of Functionals of Discrete Distributions}, journal = {ArXiV}, volume = {abs/1406.6956}, year = {2014}, url = {http://arxiv.org/abs/1406.6956} }
@inproceedings{JHW:16, author = {Jiao, Jiantao and Han, Yanjun and Weissman, Tsachy}, booktitle = {2016 IEEE International Symposium on Information Theory (ISIT)}, title = {Minimax estimation of the $L_1$ distance}, year = {2016}, pages = {750-754}, doi = {10.1109/ISIT.2016.7541399}, month = {July} }
@inproceedings{ValiantValiant:14, title = {An Automatic Inequality Prover and Instance Optimal Identity Testing}, author = {Valiant, Gregory and Valiant, Paul}, booktitle = {Proceedings of FOCS}, year = {2014}, note = {See also \cite{ValiantValiant:14:journal} (full version)} }
@article{ValiantValiant:14:journal, author = {Valiant, Gregory and Valiant, Paul}, title = {An Automatic Inequality Prover and Instance Optimal Identity Testing}, journal = {SIAM Journal on Computing}, volume = {46}, number = {1}, pages = {429-455}, year = {2017}, doi = {10.1137/151002526}, eprint = {https://doi.org/10.1137/151002526} }
@article{Valiant:11, author = {Valiant, Paul}, title = {Testing symmetric properties of distributions}, journal = {SIAM Journal on Computing}, publisher = {Society for Industrial and Applied Mathematics (SIAM)}, year = 2011, pages = {1927--1968}, volume = 40, number = 6 }
@inproceedings{CDVV:14, author = {Chan, Siu{-}On and Diakonikolas, Ilias and Valiant, Gregory and Valiant, Paul}, title = {Optimal Algorithms for Testing Closeness of Discrete Distributions}, booktitle = {Proceedings of SODA}, pages = {1193-1203}, year = 2014, publisher = {Society for Industrial and Applied Mathematics (SIAM)} }
@inproceedings{BFFKRW:01, author = {Batu, Tu\u{g}kan and Fischer, Eldar and Fortnow, Lance and Kumar, Ravi and Rubinfeld, Ronitt and White, Patrick}, title = {Testing random variables for independence and identity}, booktitle = {Proceedings of FOCS}, pages = {442--451}, year = {2001} }
@inproceedings{Alon:2007, author = {Alon, Noga and Andoni, Alexandr and Kaufman, Tali and Matulef, Kevin and Rubinfeld, Ronitt and Xie, Ning}, title = {Testing $k$-wise and Almost $k$-wise Independence}, booktitle = {Proceedings of STOC}, year = {2007}, pages = {496--505}, numpages = {10}, url = {http://doi.acm.org/10.1145/1250790.1250863}, doi = {10.1145/1250790.1250863}, address = {New York, NY, USA} }
@inproceedings{RX:10, author = {Rubinfeld, Ronitt and Xie, Ning}, title = {Testing Non-uniform $k$-wise Independent Distributions over Product Spaces}, booktitle = {Proceedings of ICALP}, year = {2010}, pages = {565--581}, numpages = {17}, url = {http://dl.acm.org/citation.cfm?id=1880918.1880980}, publisher = {Springer-Verlag}, address = {Berlin, Heidelberg} }
@inproceedings{ValiantValiant:11, author = {Valiant, Gregory and Valiant, Paul}, booktitle = {Proceedings of FOCS}, title = {The Power of Linear Estimators}, year = {2011}, month = oct, pages = {403-412}, doi = {10.1109/FOCS.2011.81}, issn = {0272-5428}, note = {See also \cite{ValiantValiant:10lb} and \cite{ValiantValiant:10ub}} }
@article{MdW:13:QPT:survey, author = {{Montanaro}, Ashley and {\noop{Wolf}}de Wolf, Ronald}, title = {A {S}urvey of {Q}uantum {P}roperty {T}esting}, journal = {ArXiV}, archiveprefix = {ArXiV}, volume = {abs/1310.2035}, primaryclass = {quant-ph}, year = 2013, month = oct }
@article{OW:15:QPT, author = {{O'Donnell}, Ryan and {Wright}, John}, title = {{Quantum Spectrum Testing}}, journal = {ArXiV}, archiveprefix = {arXiv}, volume = {abs/1501.05028}, primaryclass = {quant-ph}, year = 2015, month = jan }
@book{Poisson:1837, title = {Recherches sur la probabilit{\'e} des jugements en mati{\`e}re criminelle et en mati{\`e}re civile: pr{\'e}c{\'e}d{\'e}es des r{\`e}gles g{\'e}n{\'e}rales du calcul des probabilit{\'e}s}, author = {Poisson, Sim{\'e}on Denis}, url = {http://books.google.fr/books?id=uB8OAAAAQAAJ}, year = {1837}, publisher = {Bachelier} }
@inproceedings{DDS:PBD:12, author = {Daskalakis, Constantinos and Diakonikolas, Ilias and Servedio, Rocco A.}, title = {Learning {P}oisson {B}inomial {D}istributions}, booktitle = {Proceedings of STOC}, series = {STOC '12}, year = {2012}, isbn = {978-1-4503-1245-5}, location = {New York, New York, USA}, pages = {709--728}, numpages = {20}, publisher = {ACM}, address = {New York, NY, USA} }
@inproceedings{AD:14, author = {Acharya, Jayadev and Daskalakis, Constantinos}, title = {Testing {P}oisson {B}inomial {D}istributions}, booktitle = {Proceedings of SODA}, year = {2014}, chapter = {122}, pages = {1829-1840} }
@inproceedings{ADJOP:11, author = {Acharya, Jayadev and Das, Hirakendu and Jafarpour, Ashkan and Orlitsky, Alon and Pan, Shengjun}, title = {Competitive Closeness Testing}, booktitle = {Proceedings of COLT}, year = {2011}, pages = {47--68} }
@inproceedings{ADJOPS:12, author = {Acharya, Jayadev and Das, Hirakendu and Jafarpour, Ashkan and Orlitsky, Alon and Pan, Shengjun and Suresh, Ananda Theertha}, title = {Competitive Classification and Closeness Testing}, booktitle = {Proceedings of COLT}, year = {2012}, volume = {23}, pages = {22.1-22.18} }
@inproceedings{AJOS:13, author = {Acharya, Jayadev and Jafarpour, Ashkan and Orlitsky, Alon and Suresh, Ananda Theertha}, title = {A Competitive Test for Uniformity of Monotone Distributions}, booktitle = {Proceedings of AISTATS}, pages = {57--65}, year = {2013} }
@inproceedings{BKR:04, author = {Batu, Tu\u{g}kan and Kumar, Ravi and Rubinfeld, Ronitt}, title = {Sublinear algorithms for testing monotone and unimodal distributions}, booktitle = {Proceedings of STOC}, year = {2004}, pages = {381--390}, numpages = {10}, url = {http://doi.acm.org/10.1145/1007352.1007414}, doi = {10.1145/1007352.1007414}, publisher = {ACM}, address = {New York, NY, USA} }
@inproceedings{BFRV:11, author = {Bhattacharyya, Arnab and Fischer, Eldar and Rubinfeld, Ronitt and Valiant, Paul}, title = {Testing monotonicity of distributions over general partial orders}, booktitle = {Proceedings of ITCS}, year = {2011}, pages = {239-252}, ee = {http://conference.itcs.tsinghua.edu.cn/ICS2011/content/papers/38.html}, bibsource = {DBLP, http://dblp.uni-trier.de} }
@article{Birge:87, title = {On the Risk of Histograms for Estimating Decreasing Densities}, author = {Birg\'e, Lucien}, journal = {The Annals of Mathematical Statistics}, volume = {15}, number = {3}, pages = {pp. 1013-1022}, url = {http://www.jstor.org/stable/2241812}, issn = {00905364}, year = {1987}, publisher = {Institute of Mathematical Statistics} }
@inproceedings{DDSV:13, author = {Daskalakis, Constantinos and Diakonikolas, Ilias and Servedio, Rocco A. and Valiant, Gregory and Valiant, Paul}, title = {Testing $k$-modal Distributions: Optimal Algorithms via Reductions}, booktitle = {Proceedings of SODA}, year = {2013}, isbn = {978-1-611972-51-1}, location = {New Orleans, Louisiana}, pages = {1833--1852}, numpages = {20}, url = {http://dl.acm.org/citation.cfm?id=2627817.2627948}, acmid = {2627948}, publisher = {Society for Industrial and Applied Mathematics (SIAM)} }
@inproceedings{DDS:12, author = {Daskalakis, Constantinos and Diakonikolas, Ilias and Servedio, Rocco A.}, title = {Learning $k$-modal Distributions via Testing}, booktitle = {Proceedings of SODA}, year = {2012}, location = {Kyoto, Japan}, pages = {1371--1385}, numpages = {15}, url = {http://dl.acm.org/citation.cfm?id=2095116.2095224}, acmid = {2095224}, publisher = {Society for Industrial and Applied Mathematics (SIAM)} }
@inproceedings{ACS:10, author = {Adamaszek, Michat and Czumaj, Artur and Sohler, Christian}, title = {Testing Monotone Continuous Distributions on High-dimensional Real Cubes}, booktitle = {Proceedings of SODA}, year = {2010}, location = {Austin, Texas}, pages = {56--65}, numpages = {10}, url = {http://dl.acm.org/citation.cfm?id=1873601.1873607}, acmid = {1873607}, publisher = {Society for Industrial and Applied Mathematics} }
@inproceedings{CDGR:15, author = {Canonne, Cl\'ement L. and Diakonikolas, Ilias and Gouleakis, Themis and Rubinfeld, Ronitt}, title = {{T}esting {S}hape {R}estrictions of {D}iscrete {D}istributions}, booktitle = {33rd International Symposium on Theoretical Aspects of Computer Science (STACS)}, year = {2016}, note = {See also \cite{CDGR:17:journal} (full version)} }
@article{CDGR:17:journal, author = {Canonne, Cl\'ement L. and Diakonikolas, Ilias and Gouleakis, Themis and Rubinfeld, Ronitt}, title = {Testing Shape Restrictions of Discrete Distributions}, journal = {Theory of Computing Systems}, year = {2017}, pages = {1--59}, doi = {10.1007/s00224-017-9785-6}, url = {http://dx.doi.org/10.1007/s00224-017-9785-6}, note = {Also available on arXiv at \href{http://arxiv.org/abs/1507.03558}{abs/1507.03558}} }
@inproceedings{CGR:15, author = {Canonne, Cl\'ement L. and Gouleakis, Themis and Rubinfeld, Ronitt}, title = {{Sampling Correctors}}, booktitle = {Proceedings of ITCS}, pages = {93--102}, publisher = {{ACM}}, year = {2016} }
@incollection{ADK:15, title = {Optimal Testing for Properties of Distributions}, author = {Acharya, Jayadev and Daskalakis, Constantinos and Kamath, Gautam}, booktitle = {Advances in Neural Information Processing Systems 28}, editor = {C. Cortes and N.D. Lawrence and D.D. Lee and M. Sugiyama and R. Garnett and R. Garnett}, pages = {3577--3598}, year = {2015}, publisher = {Curran Associates, Inc.}, url = {http://papers.nips.cc/paper/5839-optimal-testing-for-properties-of-distributions.pdf} }
@inproceedings{CDSS:13, author = {Chan, Siu{-}On and Diakonikolas, Ilias and Servedio, Rocco A. and Sun, Xiaorui}, title = {Learning mixtures of structured distributions over discrete domains}, booktitle = {Proceedings of SODA}, pages = {1380--1394}, year = {2013} }
@inproceedings{CDSS:14, author = {Chan, Siu{-}On and Diakonikolas, Ilias and Servedio, Rocco A. and Sun, Xiaorui}, title = {Efficient density estimation via piecewise polynomial approximation}, booktitle = {Proceedings of STOC}, pages = {604--613}, publisher = {{ACM}}, year = {2014} }
@inproceedings{DKN:15, author = {Diakonikolas, Ilias and Kane, Daniel M. and Nikishkin, Vladimir }, title = {{T}esting {I}dentity of {S}tructured {D}istributions}, booktitle = {Proceedings of SODA}, year = {2015}, chapter = {123}, pages = {1841-1854}, publisher = {Society for Industrial and Applied Mathematics (SIAM)} }
@inproceedings{DKN:15:FOCS, author = {Diakonikolas, Ilias and Kane, Daniel M. and Nikishkin, Vladimir }, title = {{O}ptimal {A}lgorithms and {L}ower {B}ounds for {T}esting {C}loseness of {S}tructured {D}istributions}, booktitle = {Proceedings of FOCS}, year = {2015} }
@inproceedings{DDOST:13, author = {Constantinos Daskalakis and Diakonikolas, Ilias and O'Donnell, Ryan and Servedio, Rocco A. and Tan, Li{-}Yang}, title = {Learning {S}ums of {I}ndependent {I}nteger {R}andom {V}ariables}, booktitle = {Proceedings of FOCS}, pages = {217--226}, publisher = {{IEEE} Computer Society}, year = {2013} }
@inproceedings{ILR:12, author = {Indyk, Piotr and Levi, Reut and Rubinfeld, Ronitt}, title = {{Approximating and Testing $k$-Histogram Distributions in Sub-linear Time}}, pages = {15-22}, booktitle = {Proceedings of PODS}, year = {2012} }
@inproceedings{Canonne:16, doi = {10.1145/2902251.2902274}, url = {http://dx.doi.org/10.1145/2902251.2902274}, year = 2016, publisher = {Association for Computing Machinery ({ACM})}, author = {Cl\'ement L. Canonne}, title = {{Are Few Bins Enough: Testing Histogram Distributions}}, booktitle = {Proceedings of PODS} }
@techreport{An:96, title = {Log-concave probability distributions: theory and statistical testing}, author = {An, Mark Y.}, year = {1996}, institution = {Centre for Labour Market and Social Research, Denmark}, url = {http://EconPapers.repec.org/RePEc:fth:clmsre:96-01} }
@book{DL:01, title = {Combinatorial Methods in Density Estimation}, author = {Devroye, Luc and Lugosi, G\'abor}, isbn = {9780387951171}, lccn = {00058306}, series = {Springer Series in Statistics}, url = {http://books.google.com/books?id=jvT-sUt1HZYC}, year = {2001}, publisher = {Springer New York} }
@article{LeCam:73, title = {Convergence of estimates under dimensionality restrictions}, author = {Le Cam, Lucien}, journal = {The Annals of Mathematical Statistics}, pages = {38--53}, year = {1973}, volume = 1, issn = {0090-5364} }
@book{LeCam:86, author = {Le Cam, Lucien}, title = {Asymptotic methods in statistical decision theory}, series = {Springer Series in Statistics}, publisher = {Springer-Verlag, New York}, year = {1986}, pages = {xxvi+742}, isbn = {0-387-96307-3}, doi = {10.1007/978-1-4612-4946-7}, url = {http://dx.doi.org/10.1007/978-1-4612-4946-7} }
@incollection{Yu:97, year = {1997}, isbn = {978-1-4612-7323-3}, booktitle = {Festschrift for Lucien Le Cam}, editor = {Pollard, David and Torgersen, Erik and Yang, Grace L.}, doi = {10.1007/978-1-4612-1880-7_29}, title = {{A}ssouad, {F}ano, and {L}e {C}am}, url = {http://dx.doi.org/10.1007/978-1-4612-1880-7_29}, publisher = {Springer New York}, author = {Yu, Bin}, pages = {423-435}, language = {English} }
@article{Assouad:83, author = {Assouad, Patrice}, title = {Deux remarques sur l'estimation}, journal = {Comptes Rendus des S\'eances de l'Acad\'emie des Sciences. S\'erie I. Math\'ematique}, volume = {296}, year = {1983}, number = {23}, pages = {1021--1024}, issn = {0249-6291} }
@inproceedings{Waggoner:15, author = {Waggoner, Bo}, title = {\emph{L\({}_{\mbox{p}}\)} Testing and Learning of Discrete Distributions}, booktitle = {Proceedings of ITCS}, pages = {347--356}, publisher = {{ACM}}, year = {2015}, url = {http://doi.acm.org/10.1145/2688073.2688095}, doi = {10.1145/2688073.2688095} }
@incollection{BV:15, title = {Testing Closeness With Unequal Sized Samples}, author = {Bhattacharya, Bhaswar and Valiant, Gregory}, booktitle = {Advances in Neural Information Processing Systems 28}, editor = {C. Cortes and N.D. Lawrence and D.D. Lee and M. Sugiyama and R. Garnett and R. Garnett}, pages = {2593--2601}, year = {2015}, publisher = {Curran Associates, Inc.}, url = {http://papers.nips.cc/paper/5908-testing-closeness-with-unequal-sized-samples.pdf} }
@inproceedings{AJOS:14, author = {Acharya, Jayadev and Jafarpour, Ashkan and Orlitsky, Alon and Suresh, Ananda Theertha}, title = {Sublinear algorithms for outlier detection and generalized closeness testing}, booktitle = {2014 {IEEE} International Symposium on Information Theory (ISIT)}, pages = {3200--3204}, publisher = {{IEEE}}, year = {2014}, url = {http://dx.doi.org/10.1109/ISIT.2014.6875425}, doi = {10.1109/ISIT.2014.6875425}, timestamp = {Thu, 15 Jan 2015 17:11:46 +0100}, biburl = {http://dblp.dagstuhl.de/rec/bib/conf/isit/AcharyaJOS14c}, bibsource = {dblp computer science bibliography, http://dblp.org} }
@article{GR:14, author = {Oded Goldreich and Dana Ron}, title = {{On Sample-Based Testers}}, journal = {Electronic Colloquium on Computational Complexity (ECCC)}, volume = {20}, pages = {109}, year = {2013}, ee = {http://eccc.hpi-web.de/report/2013/109}, timestamp = {Wed, 28 Aug 2013 17:33:35 +0200} }
This file was generated by bibtex2html 1.98.