73 citations · 347 across the 51 of their papers we have counts for
4 papers · 1 filter
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…
Guaranteed Rank Minimization via Singular Value Projection
Raghu Meka, Prateek Jain, Inderjit S. Dhillon
Minimizing the rank of a matrix subject to affine constraints is a fundamental problem with many important applications in machine learning and statistics. In this paper we propose…
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…
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…