Your final project you can do one of the following:

- Study an open problem related to the topics we have been looking at in the class. You will attack this problem to the best of your abilities. If you solve it or obtain a partial result in this direction, you will present it. If not, you will single out the approach you feel was most hopeful, explain how it relates to the problem and give clear evidence why it could or couldn't work (with relevant examples and counterxamples).
- Ask a question (do not look it up from the web or a paper!) about which you feel some insight can be gained by using methods like the ones we learned in class. Then go about answering this question and report what you found out about it.

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 **F**_{2}^{n} to **F**_{2} is δ-far from having degree *d* - 1 then its *d*-uniformity measure is at most 1 - min{α_{0}, α_{1}δ2^{d}} 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 **F**_{3}? 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 2^{d}.

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.

- Alon, Bruck, Naor, Naor, and Roth: Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Ben-Aroya and Ta-Shma: Constructing Small-Bias Sets from Algebraic-Geometric Codes

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 *ε*2^{k/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.