142 citations · 752 across the 110 of their papers we have counts for
6 papers · 1 filter
A PRG for Lipschitz Functions of Polynomials with Applications to Sparsest Cut
Daniel Kane, Raghu Meka
We give improved pseudorandom generators (PRGs) for Lipschitz functions of low-degree polynomials over the hypercube. These are functions of the form psi(P(x)), where P is a low-de…
The Correct Exponent for the Gotsman-Linial Conjecture
Daniel M. Kane
We prove a new bound on the average sensitivity of polynomial threshold functions. In particular we show that a polynomial threshold function of degree in at most variables…
A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length
Daniel M. Kane
We develop a pseudorandom generator that fools degree- polynomial threshold functions in variables with respect to the Gaussian distribution and has seed length $O_{c,d}(\lo…
A Low-Depth Monotone Function that is not an Approximate Junta
Daniel M. Kane
We provide an example of a monotone Boolean function on the hypercube given by a low depth decision tree that is not well approximated by any k-junta for small k.
A proof of Andrews' conjecture on Partitions with no short sequences
Daniel M. Kane, Robert C. Rhoades
Holroyd, Liggett, and Romik introduced the following probability model. Let be independent events with probabilities under a probability measur…
A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions
Daniel M. Kane
We prove a structural result for degree- polynomials. In particular, we show that any degree- polynomial, can be approximated by another polynomial, , which can be d…