Analysis of Boolean Functions by Ryan O'Donnell

By Ryan O'Donnell

Boolean services are maybe the main simple gadgets of analysis in theoretical computing device technology. in addition they come up in different parts of arithmetic, together with combinatorics, statistical physics, and mathematical social selection. the sphere of research of Boolean services seeks to appreciate them through their Fourier remodel and different analytic equipment. this article supplies an intensive assessment of the sphere, starting with the main easy definitions and continuing to complex themes comparable to hypercontractivity and isoperimetry. every one bankruptcy encompasses a "highlight program" similar to Arrow's theorem from economics, the Goldreich-Levin set of rules from cryptography/learning conception, Håstad's NP-hardness of approximation effects, and "sharp threshold" theorems for random graph houses. The e-book comprises approximately 450 routines and will be used because the foundation of a one-semester graduate path. it may entice complex undergraduates, graduate scholars, and researchers in machine technological know-how thought and comparable mathematical fields.

Show description

Read or Download Analysis of Boolean Functions PDF

Similar machine theory books

Process Algebra for Parallel and Distributed Processing

Collects the most recent examine related to the applying of strategy Algebra to Computing Exploring cutting-edge purposes, approach Algebra for Parallel and disbursed Processing exhibits how one formal approach to reasoning—process algebra—has turn into a strong device for fixing layout and implementation demanding situations of concurrent platforms.

Essential Discrete Math for Computer Science

This e-book introduces readers to the math of desktop technology and prepares them for the mathematics they'll come across in different university classes. It contains functions which are particular to computing device technological know-how, is helping rookies to strengthen reasoning talents, and offers the elemental arithmetic important for desktop scientists.

How Noble in Reason

Man made Intelligence has already pervaded our lives in such a lot of sophisticated methods, yet how will people react to the construction of a very sentient tremendous desktop: a hyper-intelligent mind with no physique who's as omniscient and omnipresent because the net itself? How will humans process whatever that's distinguishable from a human simply in its visual appeal?

Pristine Perspectives on Logic, Language, and Computation: ESSLLI 2012 and ESSLLI 2013 Student Sessions. Selected Papers

The ecu summer time college in common sense, Language and knowledge (ESSLLI) is prepared each year via the organization for common sense, Language and data (FoLLI) in several websites round Europe. the main target of ESSLLI is at the interface among linguistics, common sense and computation. ESSLLI deals foundational, introductory and complicated classes, in addition to workshops, masking a large choice of themes in the 3 components of curiosity: Language and Computation, Language and good judgment, and common sense and Computation.

Extra resources for Analysis of Boolean Functions

Example text

This is another good example of being able to “read off” an interesting combinatorial property of a Boolean function from its Fourier expansion. In the special case that f : {−1, 1}n → {−1, 1} is monotone there is a much simpler way to read off its influences: they are the degree-1 Fourier coefficients. In what follows, we write f (i) in place of f ({i}). 21. If f : {−1, 1}n → {−1, 1} is monotone, then Inf i [f ] = f (i). Proof. , Di f (x) is the 0-1 indicator that i is pivotal for x. 19. 22. Let f : {−1, 1}n → {−1, 1} be transitive-symmetric and √ monotone.

We also define I(ρ) [f ] = n i=1 (ρ) Inf i [f ]. 53. I(ρ) [f ] = d Stabρ [f ] dρ = n k=1 kρ k−1 · Wk [f ]. (ρ) The ρ-stable influence Inf i [f ] increases from f (i)2 up to Inf i [f ] as ρ increases from 0 to 1. For 0 < ρ < 1 there isn’t an especially natural combi(ρ) natorial interpretation for Inf i [f ] beyond Stabρ [Di f ]; however, we will see later that the stable influences are technically very useful. 54. Suppose f : {−1, 1}n → R has Var[f ] ≤ 1. Given 0 < δ, ≤ 1, let J = {i ∈ [n] : Inf i(1−δ) [f ] ≥ }.

Proof. Certainly |J | ≤ I(1−δ) [f ]/ so it remains to verify I(1−δ) [f ] ≤ 1/δ. 53 with Var[f ] = k=0 Wk [f ] term by term, it suffices to show that (1 − δ)k−1 k ≤ 1/δ for all k ≥ 1. 45. It’s good to think of the set J in this proposition as the “notable” coordinates for function f . , the parity function χ[n] has all n of its influences equal to 1). 5. 33). Unfortunately, as soon as there are 3 (or more) candidates the problem of social choice becomes much more difficult. For example, suppose we have candidates a, b, and c, and each of n voters has a ranking of them.

Download PDF sample

Rated 4.90 of 5 – based on 31 votes