Analysis of Boolean Functions at CMU - Lecture 23: Open problems

Value of the Information & Strength of the Argument

The lecture provides a high-value overview of several central open problems in the analysis of Boolean functions. O’Donnell explains each problem clearly, motivates it with connections to other areas (e.g., quantum computing, learning theory, circuit complexity), and summarizes the state of the art. The argumentation is solid, as he carefully distinguishes between known results and conjectures, and he often gives intuition for why the conjectures are plausible. He also highlights the gaps in our knowledge, such as the enormous gap in the triangle removal problem, which underscores the importance of these open questions.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is scientifically rigorous, with O’Donnell referencing specific papers and authors for each problem. He mentions works by Green, Bhattacharya, Aaronson, Ambainis, Friedgut, Kalai, Mansour, and others, and he points to his own contributions. The sources are credible and relevant. The title accurately reflects the content, as the lecture is indeed about open problems. The presentation is well-structured, and the mathematical statements are precise, with proper definitions and conditions.

The title accurately reflects the content: a lecture dedicated to open problems in the analysis of Boolean functions.

9/10

Lecture by a leading expert in the field, based on a well-established graduate course. The content is rigorous, with references to specific papers and conjectures. The presentation is clear and the mathematical statements are precise.

Markers derived by PSI from the transcript: the creator did not define chapters.

• 00:00Introduction and overview of the lecture on open problems.
• 00:30Discussion of the triangle removal problem in additive combinatorics.
• 10:00Presentation of the Aaronson-Ambainis conjecture on influences.
• 20:00Introduction of the Fourier Entropy-Influence conjecture.
• 30:00Discussion of Mansour's conjecture and its variants.
• 40:00The inner product mod 2 conjecture in circuit complexity.
• 50:00Sensitivity conjecture and the average vs. max sensitivity problem.
• 1:00:00Further discussion and conclusion of the lecture.

• Analysis of Boolean Functions — Course website and free textbook.
• Analysis of Boolean Functions textbook — Free textbook for the course.
• Ryan O'Donnell's homepage — Instructor's academic page.
• Course page 15-859S — Course materials and syllabus.
• Panopto — Video recording platform.

• Analysis of Boolean Functions — The textbook and course materials align with the content of the lecture.