Boolean functions are central objects of study in theoretical computer science and combinatorics. Analysis of Boolean functions, and in particular Fourier analysis, has been a successful tool in the areas of circuit lower bounds, hardness of approximation, social choice, threshold phenomena, pseudo-randomness, property testing, learning theory, cryptography, quantum computing, query complexity, and others.
These applications are derived by understanding fundamental beautiful concepts in the study of Boolean functions, such as influence, noise-sensitivity, approximation by polynomials, hyper-contractivity, and the invariance-principle (connecting the discrete Boolean domain with the continuous Gaussian domain).
We will study these foundational concepts of Boolean function as well as their applications to diverse areas in TCS and combinatorics.
Textbook:
The course will be mainly based on the wonderful book by Ryan O'Donnell.
In addition, we will highlight some recent exciting results that are not covered in the book.
Time and Place: Tuesday, Thursday 5:00-6:30 PM 310 Soda Hall Instructor: Avishay Tal, Soda 635, atal@berkeley.edu Office Hours: Monday 1:30-3:30 PM Topics (not necessarily in that order):
Property Testing:
- Linearity Testing [Blum-Luby-Rubinfeld]
Influence and Hypercontractivity: - Arrow's Theorem (Kalai's Proof)
- Bonami-Beckner Theorem
- The Influence of Variables on Boolean Functions [Kahn-Kalai-Linial]
- Friedgut's Junta Theorem
Learning Theory:
- The Goldreich-Levin Algorithm (stemming from cryptography)
- Learning Shallow Circuits [Linial-Mansour-Nisan]
- Learning DNFs and Mansour's conjecture
- Learning Juntas [Mossel-O'Donnell-Servedio]
Circuit Complexity:
- Random Restrictions
- Parity not in AC0: the Switching Lemma [Håstad]
- Shrinkage of De Morgan Formulae [Håstad]
Pseudo-randomness: - Small-biased distributions [Naor-Naor] - Pseudo-randomness for low-degree functions [Bogdanov-Viola, Lovett, Viola]. - Pseudo-randomness based on random restrictions [Ajtai-Wigderson, Gopalan-Meka-Reingold-Trevisan-Vadhan, Steinke-Reingold-Vadhan] - Fractional pseudo-random generators and polarizing random walks [Chattopadhyay-Hatami-Hosseini-Lovett] Hardness-of-Approximation:
- The unique-games conjecture and its implications.
The Invariance Principle:
- Central limit theorems [Berry–Esseen]
- "Majority is Stablest" [Mossel-O'Donnell-Oleszkiewicz] Query Complexity: - The decision tree model, and its randomized, quantum, and non-deterministic analogs - The sensitivity theorem [Huang] - The polynomial method for quantum lower bounds [Beals-Buhrman-Cleve-Mosca-de Wolf] |