ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-055 | 19th May 2008 00:00

Some Topics in Analysis of Boolean Functions

RSS-Feed




TR08-055
Authors: Ryan O'Donnell
Publication: 19th May 2008 05:19
Downloads: 993
Keywords: 


Abstract:

This article accompanies a tutorial talk given at the 40th ACM STOC conference. In it, we give a brief introduction to Fourier analysis of boolean functions and then discuss some applications: Arrow?s Theorem and other ideas from the theory of Social Choice; the Bonami-Beckner Inequality as an extension of Chernoff/Hoeffding bounds to higher-degree polynomials; and, hardness for approximation algorithms.



ISSN 1433-8092 | Imprint