All reports by Author Daniel Kane:

__
TR18-074
| 23rd April 2018
__

Daniel Kane, Shachar Lovett, Shay Moran#### Generalized comparison trees for point-location problems

__
TR17-177
| 16th November 2017
__

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

Revisions: 1

__
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 Karingula#### 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

__
TR13-176
| 8th December 2013
__

Daniel Kane, Osamu Watanabe#### A Short Implicant of CNFs with Relatively Many Satisfying Assignments

Revisions: 1
,
Comments: 1

__
TR10-098
| 17th June 2010
__

Daniel Kane, Jelani Nelson#### A Derandomized Sparse Johnson-Lindenstrauss Transform

Revisions: 2

__
TR09-117
| 18th November 2009
__

Ilias Diakonikolas, Daniel Kane, Jelani Nelson#### Bounded Independence Fools Degree-2 Threshold Functions

Revisions: 1

Daniel Kane, Shachar Lovett, Shay Moran

Let $H$ be an arbitrary family of hyper-planes in $d$-dimensions. We show that the point-location problem for $H$

can be solved by a linear decision tree that only uses a special type of queries called \emph{generalized comparison queries}. These queries correspond to hyperplanes that can be written as a linear ...
more >>>

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 Karingula

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

Daniel Kane, Osamu Watanabe

Consider any Boolean function $F(X_1,\ldots,X_N)$ that has more than $2^{-N^{d}}$ satisfying assignments and that can be expressed by a CNF formula with at most $N^{1+e}$ clauses for some $d>0$ and $e>0$ such that $d+e$ is less than $1$ (*). Then how many variables do we need to fix in order ... more >>>

Daniel Kane, Jelani Nelson

Recent work of [Dasgupta-Kumar-Sarl\'{o}s, STOC 2010] gave a sparse Johnson-Lindenstrauss transform and left as a main open question whether their construction could be efficiently derandomized. We answer their question affirmatively by giving an alternative proof of their result requiring only bounded independence hash functions. Furthermore, the sparsity bound obtained in ... more >>>

Ilias Diakonikolas, Daniel Kane, Jelani Nelson

Let x be a random vector coming from any k-wise independent distribution over {-1,1}^n. For an n-variate degree-2 polynomial p, we prove that E[sgn(p(x))] is determined up to an additive epsilon for k = poly(1/epsilon). This answers an open question of Diakonikolas et al. (FOCS 2009). Using standard constructions of ... more >>>