On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition)

DOI10.1007/978-3-030-43662-9_9MaRDI QIDQ5098774zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Dana Ron

Publication date 30 August 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-43662-9_9

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Sublinear time algorithms for earth mover's distance
• New estimates for the variational distance between two distributions of a sample
• A generalization for the expected value of the earth mover's distance
• On inequalities between mutual information and variation

Cites work

• Estimating the unseen, an \(n/\log(n)\)-sample estimator for entropy and support size, shown optimal via new CLTs
• Instance Optimal Distribution Testing and Learning
• Instance optimal learning of discrete distributions
• Introduction to Property Testing
• On Sample-Based Testers

Cited in

(3)

• The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution
• Data with logical and statistical constraints
• Testing support size more efficiently than learning histograms

This page was built for publication: On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5098774)