[Theory] Theory topics course: "Analysis of Boolean Functions"

[William Hoza via Theory]

Dear theorists,

I am writing to advertise a theory topics course that I'm teaching this quarter.

Title: Analysis of Boolean Functions.
Meetings: Tuesdays and Thursdays, 12:30pm to 1:50pm, RY 178.
Course description:

A Boolean function can represent a problem we want to solve, an algorithm we want to analyze, a concept we want to learn, etc. In this course, we will use Fourier analysis to reason about Boolean functions, with applications in property testing, learning theory, pseudorandomness, and more.

Some possible topics: Linearity testing. Noise stability/sensitivity. Arrow's theorem. Dictator testing. Decision trees. Spectral concentration. The Goldreich-Levin algorithm. Total influence. Linear threshold functions. Peres's theorem. Chow's theorem. Hypercontractivity. Friedgut's junta theorem. The Kahn-Kalai-Linial theorem. The Friedgut-Kalai-Naor theorem. Bounded-depth circuits. Random restrictions. The Linial-Mansour-Nisan theorem. Fourier growth. Mansour's theorem. Read-once branching programs. Small-bias distributions. Pseudorandom generators from polarizing random walks. The Gaussian noise operator. Hermite polynomials. Invariance principles.

Course webpage: https://williamhoza.com/teaching/autumn2025-analysis-of-boolean-functions/

Sincerely,
William Hoza
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250928/24263720/attachment.html>