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

__
TR18-189
| 8th November 2018
__

Ilias Diakonikolas, Daniel Kane#### Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications)

Ilias Diakonikolas, Themis Gouleakis, Daniel Kane, John Peebles, Eric Price

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 >>>

Ilias Diakonikolas, Daniel Kane

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 >>>