73 citations · 347 across the 51 of their papers we have counts for
4 papers · 1 filter
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing
Nikhil Bansal, Haotian Jiang, Raghu Meka +2
A well-known result of Banaszczyk in discrepancy theory concerns the prefix discrepancy problem (also known as the signed series problem): given a sequence of unit vectors in $…
Efficiently Learning Any One Hidden Layer ReLU Network From Queries
Sitan Chen, Adam R Klivans, Raghu Meka
Model extraction attacks have renewed interest in the classic problem of learning neural networks from queries. In this work we give the first polynomial-time algorithm for learnin…
On the Power of Preconditioning in Sparse Linear Regression
Jonathan Kelner, Frederic Koehler, Raghu Meka +1
Sparse linear regression is a fundamental problem in high-dimensional statistics, but strikingly little is known about how to efficiently solve it without restrictive conditions on…
Random restrictions and PRGs for PTFs in Gaussian Space
Zander Kelley, Raghu Meka
A polynomial threshold function (PTF) is a function of the form where is a polynomial of degree at most …