Showing cs.CCShow all
2 papers · 1 filter
cs.CC2012
Analysis of Boolean Functions
Li-Yang Tan
Scribe notes from the 2012 Barbados Workshop on Computational Complexity. A series of lectures on Analysis of Boolean Functions by Ryan O'Donnell, with a guest lecture by Per Austr…
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…