Testing Probability Distributions using Conditional Samples
From MaRDI portal
Publication:5255008
DOI10.1137/130945508zbMath1328.68293arXiv1211.2664OpenAlexW2963597818MaRDI QIDQ5255008
Dana Ron, Clément L. Canonne, Rocco A. Servedio
Publication date: 11 June 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1211.2664
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items
Big Data on the Rise?, On the uniqueness of possibilistic measure of uncertainty and information, Where do we stand on measures of uncertainty, ambiguity, fuzziness, and the like?, Generalized information theory, Efficient parameter estimation of truncated Boolean product distributions, Testing shape restrictions of discrete distributions, On the power of conditional samples in distribution testing, Proofs of Proximity for Distribution Testing, Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces, Unnamed Item, Improving and extending the testing of distributions for shape-restricted properties, Unnamed Item, Optimal Stopping Rules for Sequential Hypothesis Testing, Topics and Techniques in Distribution Testing: A Biased but Representative Sample
Cites Work
- Unnamed Item
- Unnamed Item
- Property testing. Current research and surveys
- Exact Kolmogorov and total variation distances between some familiar discrete distributions
- An Automatic Inequality Prover and Instance Optimal Identity Testing
- On the power of conditional samples in distribution testing
- On Testing Expansion in Bounded-Degree Graphs
- Property testing and its connection to learning and approximation
- Testing Symmetric Properties of Distributions
- Estimating Entropy on<tex>$m$</tex>Bins Given Fewer Than<tex>$m$</tex>Samples
- Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
- Sublinear algorithms for testing monotone and unimodal distributions
- A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete Data
- Testing monotone high‐dimensional distributions
- On the Two Different Aspects of the Representative Method: The Method of Stratified Sampling and the Method of Purposive Selection
- Robust Characterizations of Polynomials with Applications to Program Testing
- lgorithmic and Analysis Techniques in Property Testing
- Testing equivalence between distributions using conditional samples
- Optimal Algorithms for Testing Closeness of Discrete Distributions
- Testing Closeness of Discrete Distributions
- Estimating the unseen
- The Complexity of Approximating the Entropy
- Testing k-Modal Distributions: Optimal Algorithms via Reductions
- Concentration of Measure for the Analysis of Randomized Algorithms
