Linearity Testing over the Biased Cube

on YouTube ↗01h 00m

" summary

Gives a 4-query p-biased test (queries marginally p-distributed) that works for p in (1/2,2/3), with perfect completeness and soundness 1/2; constructs a pairwise‑independent 4-bit distribution nu whose supported tuples sum to zero so w = x+y+z, then checks f(w)=f(x)+f(y)+f(z). Analysis reduces acceptance ≥1/2+δ to a structural random‑restriction theorem (restricted functions correlated to a linear imply f ≈ linear×low‑degree), uses a new direct‑product test, noise operators and the Mossel invariance principle, and yields the claimed 1%‑regime guarantee.

AI-written summary · about

" chapters (10)

1. 0:00Linearity testing over biased cube
2. 1:27Restriction and theorem
3. 8:27Biased linearity testing results
4. 11:59p-biased linearity testing
5. 19:50Four-query test in 1% regime
6. 23:48Random restriction theorem
7. 37:50Proof sketch of restriction theorem
8. 48:42Direct product testing setup
9. 53:48New direct product test
10. 57:15Q&A