All reports by Author Daniel Kane:

__
TR24-031
| 22nd February 2024
__

Daniel Kane, Anthony Ostuni, Kewen Wu#### Locality Bounds for Sampling Hamming Slices

Revisions: 1

__
TR22-178
| 8th December 2022
__

Ilias Diakonikolas, Christos Tzamos, Daniel Kane#### A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning

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

Daniel Kane, Anthony Ostuni, Kewen Wu

Spurred by the influential work of Viola (Journal of Computing 2012), the past decade has witnessed an active line of research into the complexity of (approximately) sampling distributions, in contrast to the traditional focus on the complexity of computing functions.

We build upon and make explicit earlier implicit results of ... more >>>

Ilias Diakonikolas, Christos Tzamos, Daniel Kane

The Forster transform is a method of regularizing a dataset

by placing it in {\em radial isotropic position}

while maintaining some of its essential properties.

Forster transforms have played a key role in a diverse range of settings

spanning computer science and functional analysis. Prior work had given

{\em ...
more >>>

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