Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JOHN PEEBLES:
All reports by Author John Peebles:

TR17-133 | 7th September 2017
Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price

Sample-Optimal Identity Testing with High Probability

We study the problem of testing identity against a given distribution (a.k.a. goodness-of-fit) with a focus on the high confidence regime. More precisely, given samples from an unknown distribution $p$ over $n$ elements, an explicitly given distribution $q$, and parameters $0< \epsilon, \delta < 1$, we wish to distinguish, {\em ... more >>>


TR16-178 | 11th November 2016
Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price

Collision-based Testers are Optimal for Uniformity and Closeness

Comments: 1

We study the fundamental problems of (i) uniformity testing of a discrete distribution,
and (ii) closeness testing between two discrete distributions with bounded $\ell_2$-norm.
These problems have been extensively studied in distribution testing
and sample-optimal estimators are known for them~\cite{Paninski:08, CDVV14, VV14, DKN:15}.

In this work, we show ... more >>>




ISSN 1433-8092 | Imprint