%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ifnum\withbiblioconversion=0 @string{cacm = {CACM}} @string{ipl = {IPL}} @string{jacm = {JACM}} @string{jcss = {JCSS}} @string{sicomp ={SICOMP}} @string{sidma ={SIDMA}} @string{tcs = { TCS}} @string{rsa={RSA}} @string{ieeeit={IEEE-IT}} @string{eccc={ECCC}} @string{transalg = {TALG}} @string{fntcs = {FnTCS}} @string{fntml = {FnTML}} @string{ml = {ML}} @string{jofapp = {J. of Ineq. App.}} @string{jofstatphys = {J. Stat. Phys.}} @string{infcomp={Inf. Comp.}} @string{infctrl={Inf. Cont.}} @string{beatcs = {BEATCS}} @string{annmathstat = {Ann. Math. Stat.}} @string{annstat = {Ann. Stat.}} @string{annproba = {Ann. Probab.}} @string{theorycompsyst = {Theory Comput. Syst.}} @string{theorycomp = {Theory Comput.}} @string{operletters = {Oper. Res. Lett.}} \else @string{cacm = {Communications of the ACM}} @string{ipl = {Information Processing Letters}} @string{jacm = {Journal of the ACM}} @string{jcss = {Journal of Computer and System Sciences}} @string{sicomp ={SIAM Journal on Computing}} @string{sidma ={SIAM Journal on Discrete Math}} @string{tcs = {Theoretical Computer Science}} @string{rsa={Random Structures and Algorithms}} @string{ieeeit={IEEE Transactions on Information Theory}} @string{eccc={Electronic Colloquium on Computational Complexity (ECCC)}} @string{transalg = {Transactions on Algorithms}} @string{fntcs = {Foundations and Trends in Theoretical Computer Science}} @string{fntml= {Foundations and Trends in Machine Learning}} @string{ml = {Machine Learning}} @string{jofapp = {Journal of Inequalities and Applications}} @string{jofstatphys = {Journal of Statistical Physics}} @string{infcomp={Information and Computation}} @string{infctrl={Information and Control}} @string{beatcs = {Bulletin of the European Association for Theoretical Computer Science}} @string{annmathstat = {The Annals of Mathematical Statistics}} @string{annstat = {The Annals of Mathematical Statistics}} @string{annproba = {The Annals of Probability}} @string{theorycompsyst = {Theory of Computing Systems}} @string{theorycomp = {Theory of Computing}} @string{operletters = {Operations Research Letters}} \fi @string{comcomp = {Computational Complexity}} @string{arxiv = {ArXiV}} @string{arxiveprints = {ArXiV e-prints}} @string{stoc98 = {Proceedings of STOC}} @string{stoc99 = {Proceedings of STOC}} @string{stoc00 = {Proceedings of STOC}} @string{stoc01 = {Proceedings of STOC}} @string{stoc02 = {Proceedings of STOC}} @string{stoc03 = {Proceedings of STOC}} @string{stoc04 = {Proceedings of STOC}} @string{stoc05 = {Proceedings of STOC}} @string{stoc06 = {Proceedings of STOC}} @string{stoc07 = {Proceedings of STOC}} @string{stoc08 = {Proceedings of STOC}} @string{stoc09 = {Proceedings of STOC}} @string{stoc10 = {Proceedings of STOC}} @string{stoc11 = {Proceedings of STOC}} @string{stoc12 = {Proceedings of STOC}} @string{stoc13 = {Proceedings of STOC}} @string{stoc14 = {Proceedings of STOC}} @string{stoc15 = {Proceedings of STOC}} @string{focs98 = {Proceedings of FOCS}} @string{focs99 = {Proceedings of FOCS}} @string{focs00 = {Proceedings of FOCS}} @string{focs01 = {Proceedings of FOCS}} @string{focs02 = {Proceedings of FOCS}} @string{focs03 = {Proceedings of FOCS}} @string{focs04 = {Proceedings of FOCS}} @string{focs05 = {Proceedings of FOCS}} @string{focs06 = {Proceedings of FOCS}} @string{focs07 = {Proceedings of FOCS}} @string{focs08 = {Proceedings of FOCS}} @string{focs09 = {Proceedings of FOCS}} @string{focs10 = {Proceedings of FOCS}} @string{focs11 = {Proceedings of FOCS}} @string{focs12 = {Proceedings of FOCS}} @string{focs13 = {Proceedings of FOCS}} @string{focs14 = {Proceedings of FOCS}} @string{focs15 = {Proceedings of FOCS}} @string{focs16 = {Proceedings of FOCS}} @string{soda99 = {Proceedings of SODA}} @string{soda00 = {Proceedings of SODA}} @string{soda01 = {Proceedings of SODA}} @string{soda02 = {Proceedings of SODA}} @string{soda03 = {Proceedings of SODA}} @string{soda04 = {Proceedings of SODA}} @string{soda05 = {Proceedings of SODA}} @string{soda06 = {Proceedings of SODA}} @string{soda07 = {Proceedings of SODA}} @string{soda08 = {Proceedings of SODA}} @string{soda09 = {Proceedings of SODA}} @string{soda10 = {Proceedings of SODA}} @string{soda11 = {Proceedings of SODA}} @string{soda12 = {Proceedings of SODA}} @string{soda13 = {Proceedings of SODA}} @string{soda14 = {Proceedings of SODA}} @string{soda15 = {Proceedings of SODA}} @string{random07 = {Proceedings of RANDOM}} @string{pods12 = {Proceedings of PODS}} @string{pods16 = {Proceedings of PODS}} @string{icalp10 = {Proceedings of ICALP}} @string{icalp12 = {Proceedings of ICALP}} @string{icalp13 = {Proceedings of ICALP}} @string{icalp14 = {Proceedings of ICALP}} @string{icalp15 = {Proceedings of ICALP}} @string{itcs11 = {Proceedings of ITCS}} @string{itcs13 = {Proceedings of ITCS}} @string{itcs14 = {Proceedings of ITCS}} @string{itcs15 = {Proceedings of ITCS}} @string{itcs16 = {Proceedings of ITCS}} @string{colt11 = {Proceedings of COLT}} @string{colt12 = {Proceedings of COLT}} @string{colt13 = {Proceedings of COLT}} @string{colt15 = {Proceedings of COLT}} @string{colt16 = {Proceedings of COLT}} @string{aistats = {Proceedings of AISTATS}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @inproceedings{ABR:16, author = {Maryam Aliakbarpour and Eric Blais and Ronitt Rubinfeld}, title = {Learning and Testing Junta Distributions}, booktitle = colt16, 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 = focs16, 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 = eccc, volume = {23}, pages = {15}, year = {2016} } %% Communication complexity @article{BBM:12, author = {Blais, Eric and Brody, Joshua and Matulef, Kevin}, title = {Property Testing Lower Bounds via Communication Complexity}, journal = comcomp, 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 = 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 = 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} } % Outside the field @article{Ma:81:Physics, year = {1981}, issn = {0022-4715}, journal = jofstatphys, 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 = annmathstat, 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" } %%%% Surveys @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 = jacm, 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 = beatcs, volume = {75}, pages = {97--126}, year = {2001}, } @article{Survey:Ron:08, title={{Property Testing: A Learning Theory Perspective}}, journal=fntml, 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 = fntcs, 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} } % Program checking @article{RS:96, author = {Rubinfeld, Ronitt and Sudan, Madhu}, title = {Robust Characterization of Polynomials with Applications to Program Testing}, journal = sicomp, 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 = jcss, volume = {47}, pages = {549-595}, year = {1993}, note = {An earlier version of this work appeared in STOC'90} } %%%% Tools and preliminaries @article{Scheffe:47, author = {Scheff\'e, Henry}, doi = {10.1214/aoms/1177730390}, journal = annmathstat, 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 = operletters, 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 = jacm, 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 = annmathstat, 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 = annproba, 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 = jofapp, 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 = jcss, 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 = theorycompsyst, 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} } %%%% Testing uniformity and identity @article{GRexp:00, author = {Goldreich, Oded and Ron, Dana}, title = {On Testing Expansion in Bounded-Degree Graphs}, journal = 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 = focs00, 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 = jacm, 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 = ieeeit, volume = {54}, number = {10}, year = {2008}, pages = {4750-4755}, ee = {http://dx.doi.org/10.1109/TIT.2008.928987} } %% Evaluation @inproceedings{BRY:14, author = {Berman, Piotr and Raskhodnikova, Sofya and Yaroslavtsev, Grigory}, title = {${L}_p$-testing}, booktitle = stoc14, 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 = rsa, 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} } %% Extended @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 = icalp14, 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 = sicomp, 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 = soda06, 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}, } %% Conditional @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 = itcs13, 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 = sicomp, 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 = soda14, 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 = colt15, year = {2015}, series = {{JMLR} Proceedings}, pages = {607--636}, } % Monotonicity: conditional+eval+extended+samp % Ack to Ron, Dana and Rubinfeld, Ronitt and Servedio, Rocco A. @inproceedings{CRRS:14, author = {Cl{\'{e}}ment L. Canonne}, title = {{B}ig {D}ata on the Rise? {T}esting Monotonicity of Distributions}, booktitle = icalp15, 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} } % Collections of distributions @article{LRR:13, author = {Levi, Reut and Ron, Dana and Rubinfeld, Ronitt}, title = {Testing Properties of Collections of Distributions}, journal = theorycomp, 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 = sidma, volume = {28}, number = {4}, pages = {1699--1724}, year = {2014}, url = {http://dx.doi.org/10.1137/120903737}, doi = {10.1137/120903737} } % Support size @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 = sicomp, year = 2009, pages = {813--842}, volume = 39, number = 3 } % Entropy @article{Paninski:04, title = {Estimating entropy on $m$ bins given fewer than $m$ samples}, author = {Paninski, Liam}, journal = ieeeit, 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 = soda15, pages = {1855--1869}, publisher = {Society for Industrial and Applied Mathematics (SIAM)}, year = {2015} } %% Valiant--Valiant UB, LB and overall paper on symmetric properties @article{ValiantValiant:10lb, author = {Valiant, Gregory and Valiant, Paul}, title = {A {CLT} and tight lower bounds for estimating entropy}, journal = 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 = 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 = focs14, 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 = sicomp, 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 = sicomp, 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 = soda14, 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 = focs01, 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 = stoc07, 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 = icalp10, 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}, % title = {{Estimating the unseen: an $n/\log(n)$-sample estimator for % entropy and support size, shown optimal via new {CLT}s}}, % booktitle = stoc11, % year = {2011}, % pages = {685-694}, % note = {See also \cite{ValiantValiant:10lb} and \cite{ValiantValiant:10ub}} %} @inproceedings{ValiantValiant:11, author = {Valiant, Gregory and Valiant, Paul}, booktitle = focs11, 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 } % PBD's @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 = stoc12, 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 = soda14, year = {2014}, chapter = {122}, pages = {1829-1840} } % Competitive closeness testing @inproceedings{ADJOP:11, author = {Acharya, Jayadev and Das, Hirakendu and Jafarpour, Ashkan and Orlitsky, Alon and Pan, Shengjun}, title = {Competitive Closeness Testing}, booktitle = colt11, 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 = colt12, 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 = aistats, pages = {57--65}, year = {2013} } % Monotonicity, k-modal @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 = stoc04, 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 = itcs11, 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 = annstat, 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 = soda13, 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 = soda12, 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 = soda10, 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}, } % Unified and structured @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 = itcs16, pages = {93--102}, publisher = {{ACM}}, year = {2016} } article{ADK:15, title = {Optimal Testing for Properties of Distributions}, author = {Acharya, Jayadev and Daskalakis, Constantinos and Kamath, Gautam}, journal = arxiv, eprint = {1507.05952}, number = {abs/1507.05952}, year = 2015, month = jul } @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 = soda13, 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 = stoc14, 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 = soda15, 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 = focs15, 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 = focs13, pages = {217--226}, publisher = {{IEEE} Computer Society}, year = {2013} } % Histograms @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 = pods12, 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 = pods16 } % Misc @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 = annstat, 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}, } %% Other not covered @inproceedings{Waggoner:15, author = {Waggoner, Bo}, title = {\emph{L\({}_{\mbox{p}}\)} Testing and Learning of Discrete Distributions}, booktitle = itcs15, pages = {347--356}, publisher = {{ACM}}, year = {2015}, url = {http://doi.acm.org/10.1145/2688073.2688095}, doi = {10.1145/2688073.2688095}, } article{BV:15, author = {Bhattacharya, Bhaswar B. and Valiant, Gregory}, title = {Testing Closeness With Unequal Sized Samples}, journal = arxiv, volume = {abs/1504.04599}, year = {2015}, url = {http://arxiv.org/abs/1504.04599}, timestamp = {Sat, 02 May 2015 17:50:32 +0200}, } @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 = 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} }