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 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 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 spirit of the course I encourage you to pursue a project on unconditional lower bounds, pseudorandom generators, or deterministic approximate counting, but if your heart is set on a reasonably related other topic that lies somewhat outside these areas, that could be okay too; discuss it with me. 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 expect to mention a number of other potential project topics in the course of the semester's lectures.
De Morgan formula lower bounds: Hastad, Tal.
Average-case formula lower bounds: Komargodski/Raz. Komargodski/Raz/Tal. Tal. Average-case AC0 formula lower bounds: Harsha/Molli/Shankar.
Top-down lower bounds for shallow circuits: Depth-3: Hastad/Jukna/Pudlak. Meir/Wigderson and Smal/Talebanfard, other papers (see introduction of Goos/Riazonov/Sofronova/Sokolov). Depth-4: Goos/Riazonov/Sofronova/Sokolov.
Other constant-depth circuit topics: Depth hierarchy theorems: Hastad (worst-case), Rossman/Servedio/Tan, Hastad/Rossman/Servedio/Tan (average case). Multi-switching lemmas and their applications to average-case lower bounds: Hastad, Impagliazzo/Matthews/Paturi. Sharp thresholds and circuit lower bounds: Gamarnik/Mossel/Zadik.
Time-space tradeoffs for branching programs: Borodin/Cook. Beame. Beame/Saks/Thatchachar.
The KRW Conjecture: The original paper of Karchmer/Raz/Wigderson; also see Edmonds/Impagliazzo/Rudich/Sgall, Hastad/Wigderson, Gavinsky/Meir/Weinstein/Wigderson, Dinur/Meir.
Formula size versus circuit size: Rossman, Rossman again.
Full-basis formula size lower bounds: Some nice notes on Neciporuk's approach for nearly-quadratic worst-case size lower bound for full-basis formulas: here and here. Weaker results giving superlinear full-basis lower bounds not based on Neciporuk/Andreev's method: Fischer/Meyer/Paterson, Babai/Pudlak/Szemeredi, Babai/Nisan/Szegedy.
PRGs for functions of halfspaces and intersections of halfspaces: Gopalan/O'Donnell/Wu/Zuckerman, O'Donnell/Servedio/Tan, Chattopadhyay/De/Servedio.
PRGs for linear threshold functions beyond bounded independence: Rabani/Shpilka, Meka/Zuckerman, Kothari/Meka, Gopalan/Kane/Meka.
Multi-switching lemmas and their applications in derandomization: Servedio/Tan, Kelley, Lyu.
PRGs for polynomial threshold functions: Meka/Zuckerman, Kane, Kane, Kane, Kane, and more Kane. O'Donnell/Servedio/Tan/Kane, Servedio/Tan (deterministic approximate counting).
Drilling down on DNFs and derandomization: De/Etessami/Trevisan/Tulsiani (PRGs). Gopalan/Meka/Reingold (sparsification, deterministic approximate counting). Trevisan (deterministic approximate counting). Luby/Velikovic/Wigderson (deterministic approximate counting). Servedio/Tan, Kelley (deterministic search). Servedio/Tan (read-k DNFs), LeComte/Tan (read-k DNFs).
It's also totally cool - in fact, more than cool - to do a project that spans both lower bounds and derandomization, or on a project not listed here.
By Thurs April 4 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.
April 16 and April 23 (in-class): Do your project presentation (details below)
By Thursday May 2, 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 20 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 two or at most three for your project. If you are working in a group, each student should participate in the presentation.