73 citations · 347 across the 51 of their papers we have counts for
4 papers · 1 filter
Explicit resilient functions matching Ajtai-Linial
Raghu Meka
A Boolean function on n variables is q-resilient if for any subset of at most q variables, the function is very likely to be determined by a uniformly random assignment to the rema…
Anti-concentration for polynomials of independent random variables
Raghu Meka, Oanh Nguyen, Van Vu
We prove anti-concentration results for polynomials of independent random variables with arbitrary degree. Our results extend the classical Littlewood-Offord result for linear poly…
Pseudorandomness via the discrete Fourier transform
Parikshit Gopalan, Daniel Kane, Raghu Meka
We present a new approach to constructing unconditional pseudorandom generators against classes of functions that involve computing a linear function of the inputs. We give an expl…
Sum-of-squares lower bounds for planted clique
Raghu Meka, Aaron Potechin, Avi Wigderson
Finding cliques in random graphs and the closely related "planted" clique variant, where a clique of size k is planted in a random G(n, 1/2) graph, have been the focus of substanti…