Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > DANIEL KANE:
All reports by Author Daniel Kane:

TR20-140 | 14th September 2020
Ilias Diakonikolas, Themis Gouleakis, Daniel Kane, John Peebles, Eric Price

Optimal Testing of Discrete Distributions with High Probability

We study the problem of testing discrete distributions with a focus on the high probability regime.
Specifically, given samples from one or more discrete distributions, a property $\mathcal{P}$, and
parameters $0< \epsilon, \delta <1$, we want to distinguish {\em with probability at least $1-\delta$}
whether these distributions satisfy $\mathcal{P}$ ... more >>>


TR18-189 | 8th November 2018
Ilias Diakonikolas, Daniel Kane

Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications)

The degree-$d$ Chow parameters of a Boolean function $f: \bn \to \R$ are its degree at most $d$ Fourier coefficients.
It is well-known that degree-$d$ Chow parameters uniquely characterize degree-$d$ polynomial threshold functions
(PTFs)
within the space of all bounded functions. In this paper, we prove a robust ... more >>>




ISSN 1433-8092 | Imprint