73 citations · 347 across the 51 of their papers we have counts for
Showing 2009 · cs.CCShow all
3 papers · 2 filters
cs.CC2009★ 26 cited
An Invariance Principle for Polytopes
Prahladh Harsha, Adam Klivans, Raghu Meka
Let X be randomly chosen from {-1,1}^n, and let Y be randomly chosen from the standard spherical Gaussian on R^n. For any (possibly unbounded) polytope P formed by the intersection…
cs.CC2009★ 4 cited
Pseudorandom Generators for Polynomial Threshold Functions
Raghu Meka, David Zuckerman
We study the natural question of constructing pseudorandom generators (PRGs) for low-degree polynomial threshold functions (PTFs). We give a PRG with seed-length log n/eps^{O(d)} f…
cs.CC2009★ 25 cited
Bounding the Sensitivity of Polynomial Threshold Functions
Prahladh Harsha, Adam Klivans, Raghu Meka
We give the first non-trivial upper bounds on the average sensitivity and noise sensitivity of polynomial threshold functions. More specifically, for a Boolean function f on n vari…