On the power of conditional samples in distribution testing

DOI10.1145/2422436.2422497zbMath1362.68288arXiv1210.8338OpenAlexW1967328230MaRDI QIDQ2986902

Arie Matsliah, Eldar Fischer, Yonatan Goldhirsh, Sourav Chakraborty

Publication date: 16 May 2017

Published in: SIAM Journal on Computing, Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1210.8338

zbMATH Keywords

property testingstatistical approximationdistribution testingconditional samples

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (10)

Sampling Correctors ⋮ Big Data on the Rise? ⋮ Efficient parameter estimation of truncated Boolean product distributions ⋮ Testing shape restrictions of discrete distributions ⋮ Proofs of Proximity for Distribution Testing ⋮ Unnamed Item ⋮ Improving and extending the testing of distributions for shape-restricted properties ⋮ Unnamed Item ⋮ Testing Probability Distributions using Conditional Samples ⋮ Topics and Techniques in Distribution Testing: A Biased but Representative Sample

Cites Work

• Teachability in computational learning
• Measuring teachability using variants of the teaching dimension
• Teaching a smarter learner.
• Occam's razor
• Pseudorandom generators for space-bounded computation
• On the power of inductive inference from good examples
• A model of interactive teaching
• Learning from different teachers
• On the limits of efficient teachability
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• On the complexity of teaching
• On specifying Boolean functions by labelled examples
• An Automatic Inequality Prover and Instance Optimal Identity Testing
• On Testing Expansion in Bounded-Degree Graphs
• Property testing and its connection to learning and approximation
• Testing Symmetric Properties of Distributions
• 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
• Recent Developments in Algorithmic Teaching
• A theory of the learnable
• Testing Probability Distributions Underlying Aggregated Data
• Testing Probability Distributions using Conditional Samples
• Teaching Randomized Learners
• Probability Inequalities for Sums of Bounded Random Variables
• Optimal Algorithms for Testing Closeness of Discrete Distributions
• Algorithmic Learning Theory
• A theory of goal-oriented communication
• Testing Closeness of Discrete Distributions
• The Power of Linear Estimators
• Some 3CNF Properties Are Hard to Test
• The Complexity of Approximating the Entropy
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Combinatorial methods in density estimation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the power of conditional samples in distribution testing