8197: Analysis of Boolean Functions

I still need scribe volunteers for the last two lectures

Lecture 9: 4/18
Direct sums and products, and derandomized DP testing

Lecture 10: 4/25
Short Code, possibly a derandomized BLR test.

For the next three lectures I have

Lecture 6: 3/21 (scribe by Mat)
Invariance Principle.

Lecture 7: 4/4 (scribe by Yilei)
Guest lecture by Eric Blais. Learning?

Lecture 8: 4/11 (scribe by Omer)
Direct products and the parallel repetition theorem

Please read Section 1 in the Minicourse Lecture Notes by Ryan O'Donnell: http://www.cs.cmu.edu/~odonnell/papers/barbados-aobf-lecture-notes.pdf

$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},\dots ,(-1{)}^{a_n}):=(-1{)}^{p(a_1,\dots ,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