Your final project you can do one of the following:
You will need to give a presentation about your project on the last week of class and hand in a short report. In the presentation you can give some general background on the problem but stay focused on what you are trying to achieve, not everything relevant or irrelevant you have found out. Your report should not be a survey about the ancient history of the problem, all related problems, attempts at solving it and so on. It should focus on your ideas, hopes and understanding.
You should do the project individually. Please let me know about your project proposal by email by Fri Mar 9. You should write a paragraph or two about your proposed topic over email.
Here are some possible choices of topics. Feel also free to propose your own.
In class we saw that if a function from F2n to F2 is δ-far from having degree d - 1 then its d-uniformity measure is at most 1 - min{α0, α1δ2d} for suitable constants α0, α1. The d-uniformity has a natural extension to functions over other fields. Can you prove an analogous result for other fields, even just for F3? If not, can you give an example of a function for which the statement is false?
Hadamarty, Shpilka, and Sudan prove that a different measure with the same "query complexity" gives the desired conclusion over other fields. In work that I did with Kawachi and Tanaka we show that a different analysis of the Gowers test (due to Alon, Kaufman, Krivelevich, Litsyn, and Ron) extends to other fields, but the bound given by that analysis is off by a factor of 2d.
If a function over {0,1} is δ-far from linear, the linearity test rejects it with probability at least δ. This relationship holds even as δ approaches 1/2, so even if a function has small but noticeable correlation with linear functions, the linearity test detects this correlation.
What about higher degree tests? Samorodnitsky showed that if a function has noticeable correlation with a degree 2 polynomial, then the 3-uniformity of this function is bounded away from zero, so the corresponding test detects this correlation. But later, Lovett, Meshulam, and Samorodnitsky and Green and Tao (independently) showed that this is no longer true for degree 3 polynomials and 4-uniformity. Does there exist any test (whose number of queries is independent of the number of variables) that detects if a function has noticeable correlation with degree 3 polynomials
The Gilbert-Varshamov bound shows that there exist ε-biased sets over {0,1}n of size O(n/ε2). The best known constructions, however, do not match this bound. Recent work of Ben-Aroya and Ta-Shma makes some progress towards this goal.
Check out the list of problems from the recent Simons symposium on boolean function analysis (provided by Ryan O'Donnell). Any one of these is appropriate for a final project topic.
A distribution is ε-almost k-wise independent if it is pseudorandom for the class of k-juntas on n bits. We saw that an ε-biased distribution is ε2k/2 pseudorandom against this class and there exist ε-biased distributions of support size O(n/ε2). Is this the best possible for all ε and k?
Braverman showed that distributions with bounded independence are pseudorandom for shallow circuits, proving a conjecture of Linial and Nisan. He observed that his proof extends to ε-almost k-wise independent distributions when ε is very small (inverse superpolynomial in n). Aaronson showed that when ε is large (larger than inverse linear in n) this is no longer true. What happens in between? This is an important question that, if resolved positively, may have applications to cryptography.