Comp 760 (Fall 2024): Analysis of Boolean Functions

Evaluation (updated)

Homework (75% = 5 x 15%). There will be five assignments. The due dates are going to be announced. The assignments and the exams will be graded based on correctness rather than effort alone. Each assignment will be posted on the course web page. Your grades will be posted on mycourses.

Final Project (25%): It will entail reading a research paper and writing a short summary of it.

Class participation: Although not a formal component of the course grade (and I will not formally track your attendance), you are expected to attend most of the lectures.

Description

This course is designed for graduate students in theoretical computer science or mathematics. We shall study Boolean functions and other Combinatorial objects via tools from various areas of mathematical analysis (e.g. Discrete Fourier analysis, functional analysis, convex geometry, probability theory, representation theory). In this course, we will cover the following topics:

• Fundamentals of discrete Fourier analysis: Throughout the course, we will present basic tools and results in the area, such as the hypercontractive inequality, the KKL theorem, Junta theorems by Friedgut and Bourgain, sharp thresholds and the invariance principle.
• We will discuss several applications of Fourier analysis in areas such as property testing and theoretical machine learning.
• Applications of Fourier Analysis in Hardness of Approximation. We will discuss a prominent outstanding conjecture in theoretical computer science known as the Unique-Games Conjecture. We will use some basic results from Fourier analysis to show several consequences of this conjecture, such as the (conditional) optimality of the Goemans-Williamson algorithm for Max-Cut.
• Applications of Fourier analysis in Extremal Combinatorics, particularly in understanding set systems and some problems in additive number theory.
• Towards the end of the course, we will discuss more advanced topics, which are advances in the area that have only recently been achieved. These include the resolution of the sensitivity conjecture, an extension of the hyper-contractive inequality referred to in the literature as “global hypercontractivity.”

Prerequisites

The main prerequisite is mathematical maturity and familiarity with basic background in linear algebra, mathematics analysis, and probability theory. You must be familiar with the following concepts:

• Vector spaces, rank, eigenvalues and eigen-vectors, orthogonality.
• Random variables, probability distributions, union bound, linearity of expectation.
• Abelian groups.
• Euclidean norm and Lp norms. Cauchy-Schwarz and Holder inequality.

Policies

Academic honesty. McGill University values academic integrity. Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offences under the Code of Student Conduct and Disciplinary Procedures (see http://www.mcgill.ca/integrity for more information). Most importantly, work submitted for this course must represent your own efforts. Copying assignments or tests from any source, completely or partially, allowing others to copy your work, will not be tolerated, and they will be reported to disciplinary office.

Submission of written work in French. In accord [sic] with McGill University's Charter of Students' Rights, students in this course have the right to submit in English or in French any written work that is to be graded.