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) A presentation (either in class or in a presentation session at a TBD time outside of class); 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 two or at most three.
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 aroud 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, and others.

Note that there are many great topics besides those listed below; this is just a sampling of possibilities. In keeping with the spirit of the course I encourage you to pursue a project in "concrete" complexity theory dealing with unconditional results, but if your heart is set on a complexity-theory topic (like PCPs, average-case complexity, the complexity of counting, etc) that lies outside this theme that is OK too. Yet another option is to go into more depth on some topic that we cover in class.

**Proof complexity:**Here are various different surveys on proof complexity. See also Chapters 18 and 19 of Jukna's "Boolean function complexity" book.**Arithmetic circuit complexity:**Here is a survey by Shpilka and Yehudayoff.**Polynomial representations of Boolean functions:**A survey of Beigel on polynomials in circuit complexity, and a more recent survey of Williams on how polynomials in circuit complexity can be used for algorithm design. See also Chapter 2 of Jukna's "Boolean Function Complexity" book for basics of representing Boolean functions as real polynomials.**Fourier analysis of Boolean functions:**O'Donnell's book, videos, and other materials are a great source.**Pseudorandomness:**Here is an extensive survey of Vadhan.**Decision tree complexity, sensitivity, etc:**Here are surveys by Buhrman and de Wolf and by Hatami, Kulkarni and Pankratov.**Polynomial threshold functions:**The reading list for Kane's recent course on polynomial threshold functions covers many important recent papers; a survey on older material by Saks is here.**Time-space tradeoffs:**Chapter 10 of Savage's book covers many results.

- general topic of your project
- a list of your project partners (if any)
- a list of the main sources you expect to use for your project, and
- a paragraph or so describing what you plan to cover in your presentation.

**By Thurs March 30: Mon April 3 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.

**Dates TBD in mid/late April and early May:**
Do your project presentation (details below)

**By Thursday May 4, 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 XX minutes (it's okay to go a bit shorter but you should not go
longer).
You may work in groups of two or at most three for your project.
*
If you are working
in a group, each student should participate in the presentation.
*