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.
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.