$$f:\{0,1\}^n \to \{0,1\}$$ - main object of study

The range is {0,1}, compared to R, or [0,1], these are decision functions, and not valuation functions. This difference creates a tension familiar in life, when we have an internal valuation and need to make a hard decision based on it; and manifested in math as well, when a function is “wants” to be smooth but needs to decide.

The domain is a product space {0,1} x {0,1} x … x {0,1} consisting of n independent coordinates. Not the same as a function f:X → {0,1}, because we care how the function’s behavior is related to the structure of the domain.

The domain also has a graph structure - and the underlying Hamming metric. We will care how a function respects this structure.

Analysis : we will be interested in various statements about f “on the average”. This immediately implies an underlying distribution, and we will mostly focus on the uniform distribution. This allows us to think about n independent coordinates.

Tools

Tensor structure of the function space - Fourier basis.
Hypercube graph: expansion, eigenvectors, subgraphs and quotient graphs.
Noise operator and noisy hypercube graph; generalization to product spaces
Hypercontractivity
Central Limit Theorem & Invariance Principle

Inverse Theorems

Applications

Property testing
Inapproximability
Learning
Hardness amplification
pseudo-randomness

The Fourier Basis The space of functions f is a tensor space. Definition: Let f,g be two vectors, then the tensor product f ot g is … Let U,V be two vector spaces, then the tensor product space is U ot V spanned by all f ot g. Claim: The space of all functions on n variables is the tensor of n copies of the space of all functions on one variable. Proof: construct by example. Two possible bases for n=1, then tensorize. Standard Basis: (0,1) , (1,0) and Fourier Basis: (1,1) , (1,-1) Tensorize and get the standard and Fourier basis. Define hat f_S, Claim: orthogonality Proof: using product property of tensors. Claim: parseval Linearity Testing A Boolean function can also be written as p:GF2^n → GF2 Define linear, show local characterization, and explain “robust” version (noise is here!). Talk about property testing, quasirandomness, and how this kind of thinking helps understand whether a characterization is inherent, and how so. Theorem: BLR .. Proof: Two proofs. First, ”elementary”, try to find the linear function and then prove that it is good. Second, using Fourier analysis. Technically, move back from p to f by shifting -1 → 1 and 1 → 0. Given $$p:\{0,1\}^n\to\{0,1\}$$ we define $$f:\{-1,1\}^n\to\{-1,1\}$$ by $$ f((-1)^{a_1},\ldots,(-1)^{a_n} ) := (-1)^{p(a_1,\ldots,a_n)} $$ Interpret as tensor testing Claim: $$\sum_S \hat f_S ^3 = E [ f(x)f(y)f(xy) ] $$ Compare with the original BLR proof: Define g(x) = E_y [ f(y)f(xy) ]. The Fourier transform of g has $$\hat g_S = \hat f_S^2$$ and the proof above looks at the correlation of g with f. In the BLR proof we look at sgn(g) = the majority vote, and show that is is a linear function itself & close to f