Fetching the paper…
Reading the bibliography…
A recent model for property testing of probability distributions (Chakraborty et al., ITCS 2013, Canonne et al., SICOMP 2015) enables tremendous savings in the sample complexity of testing algorithms, by allowing them to condition the sampling on subsets of the domain.
The detection of defective members of large populations
Robert Dorfman · 1943
Earlier work this paper cites.
The tail of the hypergeometric distribution
Vasek Chvátal · 1979
Earlier work this paper cites.
On approximation algorithms for #P
Larry J. Stockmeyer · 1985
Earlier work this paper cites.
Randomized Algorithms
Rajeev Motwani and Prabhakar Raghavan · 1995
Earlier work this paper cites.
Balls and Bins: A Study in Negative Dependence
Devdatt P. Dubhashi and Desh Ranjan · 1996
Earlier work this paper cites.
Testing that distributions are close
Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White · 2000
Earlier work this paper cites.
Combinatorial Group Testing and Its Applications
Dingzhu Du and Frank K. Hwang · 2000
Earlier work this paper cites.
On testing expansion in bounded-degree graphs
Oded Goldreich and Dana Ron · 2000
Earlier work this paper cites.
A Survey on Combinatorial Group Testing Algorithms with Applications to DNA Library Screening
Hung Q. Ngo and Ding-Zhu Du · 2000
Earlier work this paper cites.
Testing random variables for independence and identity
Tuğkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, and Patrick White · 2001
Earlier work this paper cites.
The art of uninformed decisions: A primer to property testing
Eldar Fischer · 2001
Earlier work this paper cites.
Sublinear algorithms for testing monotone and unimodal distributions
Tuğkan Batu, Ravi Kumar, and Ronitt Rubinfeld · 2004
Earlier work this paper cites.
Analysis of a greedy active learning strategy
Sanjoy Dasgupta · 2005
Earlier work this paper cites.
Streaming and sublinear approximation of entropy and information distances
Sudipto Guha, Andrew McGregor, and Suresh Venkatasubramanian · 2006
Earlier work this paper cites.
A coincidence-based test for uniformity given very sparsely sampled discrete data
Liam Paninski · 2008
Earlier work this paper cites.
Property Testing: A Learning Theory Perspective
Dana Ron · 2008
Earlier work this paper cites.
Strong lower bounds for approximating distributions support size and the distinct elements problem
Sofya Raskhodnikova, Dana Ron, Amir Shpilka, and Adam Smith · 2009
Cited alongside, same era.
Testing monotone high-dimensional distributions
Ronitt Rubinfeld and Rocco A. Servedio · 2009
Cited alongside, same era.
Active learning literature survey
Burr Settles · 2009
Cited alongside, same era.
Testing closeness of discrete distributions
Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White · 2010
Cited alongside, same era.
Property Testing: Current Research and Surveys
Oded Goldreich, editor · 2010
Cited alongside, same era.
Algorithmic and analysis techniques in property testing
Dana Ron · 2010
Approximating and Testing k k -Histogram Distributions in Sub-linear Time
Piotr Indyk, Reut Levi, and Ronitt Rubinfeld · 2012
Later among the works it cites.
Taming Big Probability Distributions
Ronitt Rubinfeld · 2012
Later among the works it cites.
Testing properties of collections of distributions
Reut Levi, Dana Ron, and Ronitt Rubinfeld · 2013
Later among the works it cites.
Optimal algorithms for testing closeness of discrete distributions
Siu-On Chan, Ilias Diakonikolas, Gregory Valiant, and Paul Valiant · 2014
Closest in time.
Non-adaptive group testing: Explicit bounds and novel algorithms
Chun Lam Chan, Sidharth Jaggi, Venkatesh Saligrama, and Samar Agnihotri · 2014
Closest in time.
Testing probability distributions underlying aggregated data
Clément L. Canonne and Ronitt Rubinfeld · 2014
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
A CLT and tight lower bounds for estimating entropy
Gregory Valiant and Paul Valiant · 2010
Cited alongside, same era.
Estimating the unseen: A sublinear-sample canonical estimator of distributions
Gregory Valiant and Paul Valiant · 2010
Cited alongside, same era.
Theory of Randomized Search Heuristics: Foundations and Recent Developments
Anne Auger and Benjamin Doerr · 2011
Cited alongside, same era.
Competitive closeness testing
Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, and Shengjun Pan · 2011
Cited alongside, same era.
Testing monotonicity of distributions over general partial orders
Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, and Paul Valiant · 2011
Cited alongside, same era.
Testing symmetric properties of distributions
Paul Valiant · 2011
Cited alongside, same era.
Bertinoro Workshop on Sublinear Algorithms 2014 (suggested by Eldar Fischer). Available at http://sublinear.info/66
List of Open Problems in Sublinear Algorithms: Problem 66 · 2014
Closest in time.
Adaptive estimation in weighted group testing
Jayadev Acharya, Clément L. Canonne, and Gautam Kamath · 2015
Closest in time.
A Survey on Distribution Testing: your data is Big, but is it Blue?
Clément L. Canonne · 2015
Closest in time.
Testing probability distributions using conditional samples
Clément L. Canonne, Dana Ron, and Rocco A. Servedio · 2015
Closest in time.
Faster algorithms for testing under conditional sampling
Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapathi, and Ananda Theertha Suresh · 2015
Closest in time.
On the power of conditional samples in distribution testing
Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah · 2016
Closest in time.
The power of an example: Hidden set size approximation using group queries and conditional sampling
Dana Ron and Gilad Tsur · 2016
Closest in time.
An automatic inequality prover and instance optimal identity testing
Gregory Valiant and Paul Valiant · 2017
Closest in time.
Yes, Virginia, there is a Santa Claus — Wikipedia, The Free Encyclopedia, 2017
Wikipedia · 2017
Closest in time.