Some topics in analysis of boolean functions

2008/05/17 by Ryan O’Donnell · 3 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Optimization and Search Problems #Arrow #Extension (predicate logic) #Boolean function #Discrete mathematics #Stone's representation theorem for Boolean algebras #Computer science #Social choice theory #Parity function #Mathematics #Algebra over a field #Boolean expression #Two-element Boolean algebra #Mathematical economics #Pure mathematics

paper · open access · doi:10.1145/1374376.1374458

openalex publication_date 2008/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

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.

Citations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Probabilistic checking of proofs
• A Difficulty in the Concept of Social Welfare
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Inequalities in Fourier Analysis
• On the power of unique 2-prover 1-round games
• Proof verification and the hardness of approximation problems
• Logarithmic Sobolev Inequalities
• The Elementary Statistics of Majority Voting

Cited by

• Symposium on Theory of Computing [wikipedia]