73 citations · 347 across the 51 of their papers we have counts for
Showing 2012 · cs.CCShow all
3 papers · 2 filters
cs.CC2012
A PRG for Lipschitz Functions of Polynomials with Applications to Sparsest Cut
Daniel Kane, Raghu Meka
We give improved pseudorandom generators (PRGs) for Lipschitz functions of low-degree polynomials over the hypercube. These are functions of the form psi(P(x)), where P is a low-de…
cs.CC2012
Better Pseudorandom Generators from Milder Pseudorandom Restrictions
Parikshit Gopalan, Raghu Meka, Omer Reingold +2
We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pse…
cs.CC2012★ 4 cited
DNF Sparsification and a Faster Deterministic Counting Algorithm
Parikshit Gopala, Raghu Meka, Omer Reingold
Given a DNF formula on n variables, the two natural size measures are the number of terms or size s(f), and the maximum width of a term w(f). It is folklore that short DNF formulas…