Explore a comprehensive lecture on the Analysis of Boolean Functions, focusing on Restrictions and the Goldreich--Levin Theorem. Delve into key concepts such as the Expected Square, properties and corollaries of the Goldreich-Levin Theorem, decision trees, and pseudocode. Learn from Ryan O'Donnell's graduate-level course at Carnegie Mellon University, which covers advanced topics in computer science and mathematics. Gain insights into the practical applications of boolean function analysis and enhance your understanding of complex algorithms and theorems in this field.
Analysis of Boolean Functions - Restrictions and the Goldreich-Levin Theorem
Overview
Syllabus
Intro
Example
Method
Discussion
Expected Square
GoldreichLevin Theorem
Properties
corollary
collection L
decision tree
pseudocode
Proof of correctness
Taught by
Ryan O'Donnell
