142 citations · 752 across the 110 of their papers we have counts for
7 papers · 1 filter
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits
Daniel M. 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 surprisin…
Properly Learning Poisson Binomial Distributions in Almost Polynomial Time
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
We give an algorithm for properly learning Poisson binomial distributions. A Poisson binomial distribution (PBD) of order is the discrete probability distribution of the sum of…
The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
An -Poisson Multinomial Distribution (PMD) is a random variable of the form , where the 's are independent random vectors supported on the set of…
Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions
Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin
We give a general unified method that can be used for {\em closeness testing} of a wide range of univariate structured distribution families. More specifically, we design a s…
Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
We study the structure and learnability of sums of independent integer random variables (SIIRVs). For , a -SIIRV of order is the pro…
Central Limit Theorems for some Set Partition Statistics
Bobbie Chern, Persi Diaconis, Daniel M. Kane +1
We prove the conjectured limiting normality for the number of crossings of a uniformly chosen set partition of [n] = {1,2,...,n}. The arguments use a novel stochastic representatio…