16 citations · 16 across the 2 of their papers we have counts for
2 papers
cs.CC2014★ 16 cited
Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs
Thomas Steinke, Salil Vadhan, Andrew Wan
We present an explicit pseudorandom generator for oblivious, read-once, width- branching programs, which can read their input bits in any order. The generator has seed length $\…
cs.CC2012
On the Distribution of the Fourier Spectrum of Halfspaces
Ilias Diakonikolas, Ragesh Jaiswal, Rocco A. Servedio +2
Bourgain showed that any noise stable Boolean function can be well-approximated by a junta. In this note we give an exponential sharpening of the parameters of Bourgain's resul…