Testing Closeness of Discrete Distributions

No abstract is available for this paper.

• Publication year

  2010

• Venue

  JACM

• Publication date

  2010-09-27

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/2432622.2432626
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Testing Properties of Collections of Distributions

  2013influential reference
• Matrix Computations

  2011cited by this paper
• Testing the expansion of a graph

  2010cited by this paper
• Testing Non-uniform k-Wise Independent Distributions over Product Spaces

  2010cited by this paper
• Space-Efficient Estimation of Robust Statistics and Distribution Testing

  2010influential reference
• Zero-one frequency laws

  2010cited by this paper
• A near-optimal algorithm for estimating the entropy of a stream

  2010cited by this paper
• Testing monotone continuous distributions on high-dimensional real cubes

  2010influential reference
• Sublinear estimation of entropy and information distances

  2009cited by this paper
• Measuring independence of datasets

  2009cited by this paper
• Declaring independence via the sketching of sketches

  2008cited by this paper
• An Expansion Tester for Bounded Degree Graphs

  2008cited by this paper
• Testing symmetric properties of distributions

  2008cited by this paper
• A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete Data

  2008influential reference
• Sketching information divergences

  2007cited by this paper
• Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem

  2007cited by this paper
• Testing k-wise and almost k-wise independence

  2007cited by this paper
• Testing Expansion in Bounded-Degree Graphs

  2007influential reference
• Approximating entropy from sublinear samples

  2007cited by this paper
• Estimating Entropy over Data Streams

  2006cited by this paper
• Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)

  2006influential reference
• Estimating Entropy and Entropy Norm on Data Streams

  2006cited by this paper
• Elements of Information Theory

  2005cited by this paper
• Testing monotone high‐dimensional distributions

  2005cited by this paper
• Sublinear algorithms for testing monotone and unimodal distributions

  2004cited by this paper
• Property Testing in Bounded Degree Graphs

  2002influential reference
• Abstract The

  2002cited by this paper
• The complexity of approximating entropy

  2002cited by this paper
• Three theorems regarding testing graph properties

  2001cited by this paper
• Sampling algorithms: lower bounds and applications

  2001cited by this paper
• Testing random variables for independence and identity

  2001cited by this paper
• The Art of Uninformed Decisions

  2001cited by this paper
• A Review of Graph Grammars and Preview of ICGT 2002: The First International Conference on Graph Transformation.

  2001cited by this paper
• Testing that distributions are close

  2000cited by this paper
• On Testing Expansion in Bounded-Degree Graphs

  2000cited by this paper
• Property Testing

  2000cited by this paper
• Efficient Testing of Large Graphs

  2000cited by this paper
• Testing the diameter of graphs

  1999cited by this paper
• An Approximate Lp Difference Algorithm for Massive Data Streams

  1999cited by this paper
• Quick Approximation to Matrices and Applications

  1999cited by this paper
• Spot-checkers

  1998cited by this paper
• The Art of Computer Programming: Volume 3: Sorting and Searching

  1998cited by this paper
• A complete promise problem for statistical zero-knowledge

  1997influential reference
• Property testing and its connection to learning and approximation

  1996cited by this paper
• Robust Characterizations of Polynomials with Applications to Program Testing

  1996cited by this paper
• Markov chains and polynomial time algorithms

  1994cited by this paper
• Probably Almost Discriminative Learning

  1992cited by this paper
• Program Checkers for Probability Generation

  1991influential reference
• Design considerations for neyman-pearson and wald hypothesis testing

  1989cited by this paper
• Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains

  1987influential reference
• Eigenvalues and expanders

  1986cited by this paper
• The Symmetric Eigenvalue Problem

  1981cited by this paper
• Calculation of entropy from data of motion

  1981cited by this paper
• An Efficient Method for Generating Discrete Random Variables with General Distributions

  1977cited by this paper
• The Design and Analysis of Computer Algorithms

  1974cited by this paper
• Testing Statistical Hypotheses

  1959cited by this paper
• An Introduction to Probability Theory and its Applications

  1958cited by this paper
• An Introduction to Probability Theory and its Applications, Volume I

  1958cited by this paper
• On the Problem of the Most Efficient Tests of Statistical Hypotheses

  1933cited by this paper

• Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions

  2026cites this paper
• Efficient Non-Adaptive Quantum Algorithms for Tolerant Junta Testing

  2025cites this paper
• Identity Testing for Stochastic Languages

  2025cites this paper
• Replicable Distribution Testing

  2025cites this paper
• Verification of Statistical Properties: Redefining the Possible

  2025cites this paper
• Estimating Hitting Times Locally At Scale

  2025cites this paper
• Stochastic Languages at Sub-stochastic Cost

  2025cites this paper
• Monochromatic subgraphs in randomly colored dense multiplex networks

  2025cites this paper
• Distribution Testing Meets Sum Estimation

  2025cites this paper
• A Kernel Distribution Closeness Testing

  2025cites this paper
• On Differentially Private U Statistics

  2024cites this paper
• Adaptive Binning Coincidence Test for Uniformity Testing

  2024cites this paper
• Large and Small Deviations for Statistical Sequence Matching

  2024cites this paper
• Equivalence Testing: The Power of Bounded Adaptivity

  2024cites this paper
• Equivalence and Similarity Refutation for Probabilistic Programs

  2024cites this paper
• Large Deviations for Statistical Sequence Matching

  2024cites this paper
• Optimal Algorithms for Augmented Testing of Discrete Distributions

  2024cites this paper
• Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph

  2024cites this paper
• Improving Pearson's chi-squared test: hypothesis testing of distributions -- optimally

  2023cites this paper
• Striving for simplicity and effectiveness: quantum algorithm for distribution property testing

  2023cites this paper
• Uniformity Testing over Hypergrids with Subcube Conditioning

  2023cites this paper
• Testing of Horn Samplers 1

  2023cites this paper
• Testing versus estimation of graph properties, revisited

  2023cites this paper
• Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight

  2023influential citation
• On Scalable Testing of Samplers

  2023cites this paper
• Tight Lower Bound on Equivalence Testing in Conditional Sampling Model

  2023cites this paper
• Testing with Non-identically Distributed Samples

  2023cites this paper
• Succinct Quantum Testers for Closeness and k-Wise Uniformity of Probability Distributions

  2023cites this paper
• Mathematical Framework for Online Social Media Regulation

  2022cites this paper
• Mathematical Framework for Online Social Media Auditing

  2022cites this paper
• Near-Optimal Bounds for Testing Histogram Distributions

  2022cites this paper
• Evaluation of Categorical Generative Models - Bridging the Gap Between Real and Synthetic Data

  2022cites this paper
• A fourth‐moment phenomenon for asymptotic normality of monochromatic subgraphs

  2022cites this paper
• Quantum Approximate Counting for Markov Chains and Application to Collision Counting

  2022cites this paper
• New Quantum Algorithms for Computing Quantum Entropies and Distances

  2022cites this paper
• KL Divergence Estimation with Multi-group Attribution

  2022cites this paper
• Likelihood-Free Hypothesis Testing

  2022cites this paper
• Testing Distributions of Huge Objects

  2022cites this paper
• Testing Histograms Nearly Optimally

  2022cites this paper
• As Easy as ABC: Adaptive Binning Coincidence Test for Uniformity Testing

  2021cites this paper
• Generalized LRS Estimator for Min-Entropy Estimation

  2021cites this paper
• The Price of Tolerance in Distribution Testing

  2021cites this paper
• Multicalibrated Partitions for Importance Weights

  2021cites this paper
• Analysis of COVID-19 evolution based on testing closeness of sequential data

  2021cites this paper
• Testing Tail Weight of a Distribution Via Hazard Rate

  2020cites this paper
• Verifying Stochastic Hybrid Systems with Temporal Logic Specifications via Model Reduction

  2020cites this paper
• Testing Product Distributions: A Closer Look

  2020cites this paper
• Sequential Change Detection by Optimal Weighted ℓ₂ Divergence

  2020cites this paper
• Optimal testing of discrete distributions with high probability

  2020cites this paper
• Testing Determinantal Point Processes

  2020cites this paper
• A Survey on Distribution Testing: Your Data is Big. But is it Blue?

  2020cites this paper
• Quantum Communication Complexity of Distribution Testing

  2020cites this paper
• Normal approximation and fourth moment theorems for monochromatic triangles

  2020cites this paper
• Asymptotic distribution and detection thresholds for two-sample tests based on geometric graphs

  2020cites this paper
• Verifying Stochastic Hybrid Systems with Temporal Logic Specifications via Mori-Zwanzig Model Reduction

  2020cites this paper
• The Sample Complexity of Robust Covariance Testing

  2020cites this paper
• On Testing of Samplers

  2020cites this paper
• Distributed Testing of Graph Isomorphism in the CONGEST model

  2020cites this paper
• On Efficient Distance Approximation for Graph Properties

  2020cites this paper
• Complexity of Estimating Rényi Entropy of Markov Chains

  2020cites this paper
• Failures of model-dependent generalization bounds for least-norm interpolation

  2020cites this paper
• Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning

  2020cites this paper
• On Testing of Uniform Samplers ∗†

  2019cites this paper
• New Algorithms for Large Datasets and Distributions

  2019cites this paper
• Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit

  2019cites this paper
• Distribution Testing Lower Bounds via Reductions from Communication Complexity

  2019cites this paper
• Testing Mixtures of Discrete Distributions

  2019cites this paper
• 23 : 2 Quantum Chebyshev ’ s Inequality and Applications

  2019cites this paper
• Counting and Sampling Directed Acyclic Graphs for Learning Bayesian Networks

  2019cites this paper
• Testing Properties of Multiple Distributions with Few Samples

  2019cites this paper
• Distributional property testing in a quantum world

  2019cites this paper
• Estimating the Mixing Time of Ergodic Markov Chains

  2019influential citation
• Entropies and their Asymptotic Theory in the discrete case

  2019cites this paper
• Sample Amplification: Increasing Dataset Size even when Learning is Impossible

  2019cites this paper
• Quantum Walk Sampling by Growing Seed Sets

  2019cites this paper
• Concentration and Tail Bounds for Missing Mass

  2019cites this paper
• Private Testing of Distributions via Sample Permutations

  2019cites this paper
• L G ] 6 F eb 2 01 8 Recovering Structured Probability Matrices

  2018cites this paper
• Differential Privacy, Property Testing, and Perturbations

  2018cites this paper
• Two Party Distribution Testing: Communication and Security

  2018cites this paper
• D S ] 1 5 A ug 2 01 7 Generalized Uniformity Testing

  2018cites this paper
• Communication Complexity of Statistical Distance

  2018cites this paper
• Quantum fast-forwarding: Markov chains and graph property testing

  2018cites this paper
• Modern challenges in distribution testing

  2018cites this paper
• Tolerant Testing of Product Distributions

  2018cites this paper
• Second-Order Asymptotically Optimal Statistical Classification

  2018cites this paper
• Property Testing For Differential Privacy

  2018cites this paper
• The query complexity of graph isomorphism: bypassing distribution testing lower bounds

  2018cites this paper
• Quantum Chebyshev's Inequality and Applications

  2018cites this paper
• Probability-Revealing Samples

  2018cites this paper
• Differentially Private Identity and Equivalence Testing of Discrete Distributions

  2018cites this paper
• Profile Maximum Likelihood is Optimal for Estimating KL Divergence

  2018cites this paper
• Testing Symmetric Markov Chains From a Single Trajectory

  2017cites this paper
• Renyi Entropy Estimation Revisited

  2017cites this paper
• Quantum state certification

  2017influential citation
• Improved bounds for testing Dyck languages

  2017cites this paper
• Generalized Uniformity Testing

  2017cites this paper
• Property Testing of Joint Distributions using Conditional Samples

  2017cites this paper
• Testing from One Sample: Is the casino really using a riffle shuffle?

  2017cites this paper
• Differentially Private Identity and Closeness Testing of Discrete Distributions

  2017cites this paper