Projects per year
Abstract
We give a general unified method that can be used for L1 closeness testing of a wide range of univariate structured distribution families. More specifically, we design a sample optimal and computationally efficient algorithm for testing the equivalence of two unknown (potentially arbitrary) univariate distributions under the Akdistance metric: Given sample access to distributions with density functions p, q : I → R, we want to distinguish between the cases that p = q and ∥p  q∥Ak ≥ ∈ with probability at least 2/3. We show that for any k ≥ 2, ∈ > 0, the optimal sample complexity of the Akcloseness testing problem is Θ(max{k4/5/∈6/5, k1/2/∈2}). This is the first o(k) sample algorithm for this problem, and yields new, simple L1 closeness testers, in most cases with optimal sample complexity, for broad classes of structured distributions.
Original language  English 

Title of host publication  2015 IEEE 56th Annual Symposium on Foundations of Computer Science 
Publisher  Institute of Electrical and Electronics Engineers (IEEE) 
Pages  11831202 
Number of pages  20 
ISBN (Electronic)  9781467381918 
DOIs  
Publication status  Published  17 Dec 2015 
Publication series
Name  

ISSN (Print)  02725428 
Fingerprint
Dive into the research topics of 'Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions'. Together they form a unique fingerprint.Projects
 1 Finished

Sublinear Algorithms for Approximating Probability Distribution
Diakonikolas, I.
1/09/14 → 31/08/15
Project: Research