73 citations · 347 across the 51 of their papers we have counts for
4 papers · 1 filter
On the discrepancy of random low degree set systems
Nikhil Bansal, Raghu Meka
Motivated by the celebrated Beck-Fiala conjecture, we consider the random setting where there are elements and sets and each element lies in randomly chosen sets. In th…
Pseudorandom Generators for Width-3 Branching Programs
Raghu Meka, Omer Reingold, Avishay Tal
We construct pseudorandom generators of seed length that -fool ordered read-once branching programs (ROBPs) of width and length . For…
Efficient Algorithms for Outlier-Robust Regression
Adam Klivans, Pravesh K. Kothari, Raghu Meka
We give the first polynomial-time algorithm for performing linear or polynomial regression resilient to adversarial corruptions in both examples and labels. Given a sufficiently la…
Learning One Convolutional Layer with Overlapping Patches
Surbhi Goel, Adam Klivans, Raghu Meka
We give the first provably efficient algorithm for learning a one hidden layer convolutional network with respect to a general class of (potentially overlapping) patches. Additiona…