In general there are two main goals for a project in this class:
(1) You should acquire a substantial body of knowledge about the topic of your project. This will involve closely and carefully reading research literature on your specific project topic. You'll demonstrate this aspect of your project in two ways: through the presentation you give in class, and through the "background" section(s) of your project report, which should be a clear synthesis and exposition in your own words of what you learned.
(2) You should gain research experience in this area; i.e. make a serious effort to contribute to the state of knowledge on your project topic by (i) identifying an interesting open question or direction for future research related to your project topic; (ii) coming up with an approach to make progress; and (iii) working to carry out your approach. You'll demonstrate this aspect of your project by explaining in detail what you did for (i), (ii) and (iii) in the rest of your project report.
The ratio of (1) to (2) may vary between different projects. There are some projects that might involve relatively less background (but in that case you will be expected to spend more time -- and give more evidence of time well spent) -- on trying to make research progress; and there are other projects where you'll need to acquire more extensive background.
The tangible results of your project will be:
(A) A progress report (more details on this below).
(B) An in-class presentation; basically, you will give a lecture (or part of a lecture) on your topic. The goal is to give a clear overview of your topic and an accessible, self-contained (as much as possible) presentation of an important result. You should prepare carefully for this presentation.
(C) A project report due at the end of the semester. This will be the major component of your course grade and should reflect your best effort. In this report you should give clear and convincing evidence that goals (1) and (2) above were achieved.
You may work in groups of more than one person (exact size bound TBD). Expectations for projects will be calibrated according to group size.
Some potential broad topics for projects are given below. You are also encouraged to come up with your own project topic (if you do this, send me email with the project topic when you settle on it to make sure it's suitable for this class). If you're browsing around for topics, good places to look are the proceedings of FOCS (Symposium on Foundations of Computer Science), STOC (Symposium on Theory of Computing), CCC (Conference on Computational Complexity), and similar conferences, as well as journals like JACM, J. Computer & System Sciences, SIAM Journal on Computing, Information and Computation, Computational Complexity, ACM Transactions on Computation Theory, Theory of Computing, and others.
Note that there are many great topics besides those listed below; this is just a sampling of possibilities. In keeping with the topic of the course you should pursue a project related to Boolean function in one way or another, but there is no hard and fast rule on how tight this connection needs to be --- come and talk to me if your heart is set on a project for which the connection is less tight. Yet another option is to go into more depth on some topic that we cover in class (there is quite a bit more to say about all of the topics that we will cover than we will be able to say). I will mention many potential project topics in the course of the semester's lectures.
Boolean function complexity measures: There is a thriving subarea in the study of Boolean functions that defines various measures of the complexity of a Boolean function. The old survey by Burham and de Wolf is still a great source for classic result on this topic. The most spectacular result in this area in the last decade is Huang's proof of the sensitivity conjecture, which is another great project topic; the paper of Aaronson, Ben-David, Kothari, Rao and Tal studies a number of post-Huang consequences of his proof for various complexity measures. There are lots of good project topics in this general space.
Boolean function analysis and voting theory: Some papers that study how Boolean function analysis can be applied to analyze election schemes are Kalai's original paper about Arrow's Theorem (also covered in the O'Donnell textbook); Mossel's follow-up paper; and these papers by Friedgut, Kalai, Nisan, Isaksson, Kindler, and Mossel on quantitative versions of the Gibbard-Satterthwaite theorem.
Degree versus number of variables of Boolean functions: A quantitatively stronger version of the result of Nisan and Szegedy that we proved lower bounding the degree of a Boolean function that depends on all its variables was subsequently given by Chiarelli, Hatami and Saks. Related questions have also been asked for other complexity measures; for example, here is a paper by Simon giving an analogous bound for sensitivity rather than degree.
(Sharp) bounds on sensitivity of width-w DNFs, size-s DNFs, and their friends: Amano has given a sharp bound on the average sensitivity of a width-k DNF or CNF, and Boppana has given bounds on the average sensitivity of constant-depth circuits. Sharper and more sophisticated bounds were given more recently by Rossman on the average sensitivity of bounded-depth Boolean formulas (rather than circuits)
Noise sensitivity of monotone functions monotone functions: This paper by O'Donnell and Mossel studies the noise sensitivity of monotone functions and constructs some interesting extremal monotone functions along the way.
Hermite concentration of convex sets under the Gaussian distribution: This was first observed in this paper, though most of the key ideas are in earlier work.
Correlation inequalities for monotone Boolean functions: Here is Talagrand's original paper proving a quantitative version of the Harris-Kleitman correlation inequality for monotone Boolean functions. This paper gives a framework for proving (a slightly weaker version of) Talagrand's inequality as well as a quantitative version of Royen's inequality (the Gaussian Correlation Theorem) in a common framework.
Gaussian convex influences: This paper introduces a notion of "influence of direction v on symmetric convex set C in \R^n" and establishes correspondences between that notion and the familiar notion of the influence of coordinate i on Boolean function f over {-1,1}^n. Earlier work of Keller, Mossel and Sen studying a different notion of influences over \R^n is here.
Other facets of the ``monotone Boolean / convex Gaussian analogy": Various papers that touch on different aspects of this analogy can be found here, here, here, in the juxtaposition of these two papers, in the juxtaposition of these two papers, and here.
Bounds on integer weights for linear threshold functions: Here is a paper of Hastad which uses Fourier analysis to lower bound the size of the integer weights that are required to compute a particular (cleverly chosen) linear threshold function. The result is extended to low-degree polynomial threshold functions in this paper of Podolskii.
Fourier concentration and closeness to juntas: This paper of Bourgain shows that any sufficiently noise stable Boolean function is close to a junta. See this paper of O'Donnell and Kindler for a more recent, possibly (depending on taste) more readable, and quantitatively stronger version.
Algorithmic versions of Chow's theorem: Several papers have studied the problem of making Chow's theorem algorithmic, i.e. giving algorithms which take as input a (possibly noisy) version of the degree-0 and degree-1 Fourier coefficients of a linear threshold function and output (possibly an approximation of) that linear threshold function. See here and here for papers on the original algorithmic problem for LTFs, here for a paper of Diakonikolas and Kane about a degree-d PTF extension, and here for a paper by Diakonikolas and Pavlou about hardness of this problem.
Lower bounds on polynomial threshold function degree: A line of work over the past few decades has given lower bounds on polynomial threshold function degree for classes such as intersections of halfspaces and consant-depth circuits. Most of this work is due to Sherstov, with other contributions by Bun and Thaler and others; see here, here, here, here, here, and here for results along these lines.
Towards the Gotsman-Linial Theorem: Early papers studying average sensitivity and noise sensitivity of low-degree polynomial threshold functions (the topic of the Gotsman-Linial Conjecture) are here and here. The state of the art progress towards the Gotsman-Linial conjecture is due to Kane. A short paper showing that the exact original form of the conjecture is not correct, due to Chapman, is here.
Decision trees and influences: There are several other proofs of the "every decision tree has an influential variable" theorem (besides the two we did in class); here is the original proof and here is another proof due to Jain and Zhang.
Fourier-based learning from random examples: The famous Linial/Mansour/Nisan paper showed how to learn constant-depth circuits in quasipolynomial time using random examples only; papers of Hastad and Tal subsequently gave sharpenings. This paper used Sieganthaler's Theorem (without knowing it) to give a faster-than-brute-force algorithm for learning k-juntas (functions that depend on only k of the n input variables) using random examples. Work by G. Valiant subsequently gave a faster algorithm.
Fourier-based learning using queries: This paper by Mansour showed how membership queries can be used to learn DNF formuls in almost polynomial time. Subsequently, by bringing in ideas from boosting, this paper by Jackson gave a polynomial-time algorithm.
Agnostic learning, with and without queries: This is a big topic --- here is a paper that is a good starting point for agnostic learning without queries and here is a paper by Gopalan/Kalai/Klivans that is a good starting point for agnostic learning using queries.
Learning bounded low-degree polynomials: Recent work by Eskenazis and Ivanisvili showed that the problem of learning an unknown degree-d bounded, real-valued function --- i.e. a function of Fourier degree d that maps ${-1,1}^n$ to the real interval $[-1,1]$ --- can be solved using surprisingly few random examples (in particular, the dependence on $n$ is just $\log n$). The key tool is a sophisticated analytic inequality called a ``Bohnenblust-Hille type inequality'' for functions on the Boolean cube; the specific inequality that is needed is due to Defant, Mastyło and Pérez. A different paper by Eskenazis, Ivanisvili and Streck is also relevant here.
Green-Sanders and related results: A theorem of Green and Sanders shows that a Boolean function with constant spectral norm is a signed sum of constantly many indicator functions of subgroups of F_2^n. Shpilka, Tal and Volk gave a subsequent refinement of the result, as did a later paper of Sanders; see also the work of Tsang, Wong, Xie and Zhang.
Other approaches to the Berry-Esseen Theorem: In class we discussed the ``Lindeberg-style'' / ``replacement method'' proof of the Berry-Esseen theorem. There is another approach to the proof which goes through classical Fourier analysis; here is a paper by Vershynin giving a friendly version of this proof, and this version of the paper augments it with another friendly proof using Stein's method. There is a big literature in this general space; for example, here is a paper by Klartag and Sodin which gives a refinement of the Berry Esseen theorem under some (mild) additional conditions on the independent summands.
A deeper dive into invariance. We will only scratch the surface of the Invariance Principle in class; the original paper by Mossel, O'Donnell and Oleszkiewicz is a good starting point for this rich topic.
De Morgan formula lower bounds: The most powerful known lower bounds on Boolean formula size for explicit functions, due to Tal, involve Fourier analysis (as well as other ingredients).
Unconditional pseudorandom generators for functions of halfspaces, intersections of halfspaces, and polynomial threshold functions: Gopalan/O'Donnell/Wu/Zuckerman builds on the Berry-Esseen theorem (and extensions thereof) to get unconditional pseudorandom generators for functions of halfspaces. This paper builds on the average sensitivity of intersections of halfspaces result of Kane that we covered in class to get unconditional pseudorandom generators for intersections of halfspaces. This paper studies unconditional pseudorandom generators over Gaussian space for intersections of halfspaces using (among other tools) invariance principles. Meka/Zuckerman uses invariance principles to construct unconditional pseudorandom generators for polynomial threshold functions. Here are many different papers, mostly due to Kane, about unconditional pseudorandom generators for low-degree PTFs over Gaussian space.
It's also totally fine to do a project on a project not listed here.
By Wed Nov 18 at 11:59pm: Email Rocco a progress report for your project. This should be an explanation of the work you have done thus far on your project. It does not need to have the same level of technical detail as your final project report, but it should show that you have already invested a significant amount of time in working on your project. 3-5 pages is a good length to shoot for for this (note that the final project report should be an extended version of this progress report). Also, the progress report should give a more detailed explanation of what you are planning to cover in your presentation. I will give you feedback on this at least 1 week prior to your presentation.
Wed Dec 2 and Wed Dec 9 (in-class): Do your project presentation (details below)
By Friday, Dec 18, 11:59pm: Email your final project report to Rocco.
Project presentations: Student project presentations will take place on TBD dates in mid/late April and early May. Each student/group should plan to present for at most TBD minutes per person in the group (it's okay to go a bit shorter but you should not go any longer). You may work in groups of size at most TBD for your project. If you are working in a group, each student should participate in the presentation.