All reports by Author Daniel Kane:

__
TR17-177
| 16th November 2017
__

Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff#### On Communication Complexity of Classification Problems

__
TR17-132
| 7th September 2017
__

Ilias Diakonikolas, Daniel Kane, Alistair Stewart#### Sharp Bounds for Generalized Uniformity Testing

__
TR17-085
| 4th May 2017
__

Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang#### Active classification with comparison queries

__
TR17-082
| 4th May 2017
__

Daniel Kane, Shachar Lovett, Shay Moran#### Near-optimal linear decision trees for k-SUM and related problems

__
TR17-033
| 19th February 2017
__

Daniel Kane, Shachar Lovett, Sankeerth Rao#### Labeling the complete bipartite graph with no zero cycles

Revisions: 2

__
TR17-026
| 17th February 2017
__

Valentine Kabanets, Daniel Kane, Zhenjian Lu#### A Polynomial Restriction Lemma with Applications

__
TR16-177
| 11th November 2016
__

Ilias Diakonikolas, Daniel Kane, Alistair Stewart#### Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures

Revisions: 1

__
TR16-074
| 9th May 2016
__

Ilias Diakonikolas, Daniel Kane#### A New Approach for Testing Properties of Discrete Distributions

__
TR15-188
| 24th November 2015
__

Daniel Kane, Ryan Williams#### Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits

Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff

This work introduces a model of distributed learning in the spirit of Yao's communication complexity model. We consider a two-party setting, where each of the players gets a list of labelled examples and they communicate in order to jointly perform some learning task. To naturally fit into the framework of ... more >>>

Ilias Diakonikolas, Daniel Kane, Alistair Stewart

We study the problem of {\em generalized uniformity testing}~\cite{BC17} of a discrete probability distribution: Given samples from a probability distribution $p$ over an {\em unknown} discrete domain $\mathbf{\Omega}$, we want to distinguish, with probability at least $2/3$, between the case that $p$ is uniform on some {\em subset} of $\mathbf{\Omega}$ ... more >>>

Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang

We study an extension of active learning in which the learning algorithm may ask the annotator to compare the distances of two examples from the boundary of their label-class. For example, in a recommendation system application (say for restaurants), the annotator may be asked whether she liked or disliked a ... more >>>

Daniel Kane, Shachar Lovett, Shay Moran

We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry.

For example, for any constant $k$, we construct linear decision trees that solve the $k$-SUM problem on $n$ elements using $O(n \log^2 n)$ linear queries.

Moreover, the queries we use are comparison ...
more >>>

Daniel Kane, Shachar Lovett, Sankeerth Rao

Assume that the edges of the complete bipartite graph $K_{n,n}$ are labeled with elements of $\mathbb{F}_2^d$, such that the sum over

any simple cycle is nonzero. What is the smallest possible value of $d$? This problem was raised by Gopalan et al. [SODA 2017] as it characterizes the alphabet size ...
more >>>

Valentine Kabanets, Daniel Kane, Zhenjian Lu

A polynomial threshold function (PTF) of degree $d$ is a boolean function of the form $f=\mathrm{sgn}(p)$, where $p$ is a degree-$d$ polynomial, and $\mathrm{sgn}$ is the sign function. The main result of the paper is an almost optimal bound on the probability that a random restriction of a PTF is ... more >>>

Ilias Diakonikolas, Daniel Kane, Alistair Stewart

We prove the first {\em Statistical Query lower bounds} for two fundamental high-dimensional learning problems involving Gaussian distributions: (1) learning Gaussian mixture models (GMMs), and (2) robust (agnostic) learning of a single unknown mean Gaussian. In particular, we show a {\em super-polynomial gap} between the (information-theoretic) sample complexity and the ... more >>>

Ilias Diakonikolas, Daniel Kane

We study problems in distribution property testing:

Given sample access to one or more unknown discrete distributions,

we want to determine whether they have some global property or are $\epsilon$-far

from having the property in $\ell_1$ distance (equivalently, total variation distance, or ``statistical distance'').

In this work, we give a ...
more >>>

Daniel Kane, Ryan Williams

In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for ... more >>>