@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.