Projects

A project can either be a study project or a research project.

In a study project you focus on an important result, or set of results, that is not covered in detail in the course. You read the relevant papers and write a survey paper that describes the results, their motivation, their applications, and something new. "Something new" could be filling in the details of an important technical lemma that is only stated without proof (or with a sketchy proof) in the literature, or observe a simplified argument for a technical proof, or something along these lines.

A research project starts with a general goal, like "prove a weakly-non-uniform hierarchy theorem for ZPTIME," or "improve the inapproximability result for Metric TSP," or "Prove P=/=NP." Towards this goal, you read the relevant papers, try various approaches, and then you may or may not reach your goal. At the end you write a report detailing your efforts.

Study projects should be done independently. If you want to do a study project, and you strongly prefer to do collaborative work, you can arrange with a colleague to choose related topics for a study project (for example, one project could be on impossibility results for random oracles in cryptography and another could be impossibility results for obfuscation). Then you can study together, even though two different reports will have to be submitted.

A research project can be assigned to a team of two.

Examples

Any important result in complexity can be the base for a study project, and any interesting open question can the base for a research project.

Here are some examples. Ask me for the references. Many entries are "under construction". Check this page later for updates (or ask me).

• Prove a hierarchy theorem for ZPTIME. (Research project.)
  Barak, and then Fortnow and Santhanam prove hierarchy theorems for BPTIME with advice. It is open how to get similar results for ZPTIME. (Update:  a hierarchy theorem for RTIME has been announced).
• Conditional derandomization. (Study project.)
  Study some subset of the following papers:  Nisan-Wigderson (basic trade-off between average-case complexity and derandomization), Impagliazzo-Wigderson (worst-case to average-case equivalence) Sudan-Trevisan-Vadhan ("simplified" proof of Impagliazzo-Wigderson) Shaltiel-Umans (algebraic construction of pseudorandom generators).
  There is at least one interesting and perhaps feasible question here: to derive "uniform" versions of the above results, improving on partial results by Impagliazzo-Wigderson (a different paper, not the one referenced above) and Trevisan-Vadhan.
•  Theory of cryptography (many possible study projects)
  • Proof by Hastad, Impagliazzo, Levin and Luby that pseudorandom generators exist if one-way functions exist.
    Here I would really like the ambitious project of re-writing the proof, at least the non-uniform version,  with "concrete" parameters and an understandable, modular presentation.
  • The non-black-box zero-knowledge proof system of Barak
  • Positive and negative results about the random oracle model
  • Negative results on obfuscation. Here there may be room for a research project as well
  • . . .
• Unconditional Derandomization
  • Derandomization of polynomial identity testing for polynomials computed by "non-commutative branching programs"
    See the paper of Shpilka and Raz [here]
  • Derandomization of approximate counting of satisfying assignments of  DNF (project chosen by Omid)
• Average-case complexity in NP
  • Impossibility results for worst-case to average-case equivalence for NP-complete problems (Feigenbaum-Fortnow, Bogdanov-Trevisan, Viola)
  • Amplification of average-case hardness of problems in NP (O'Donnell, . . . )
• Average-case complexity of lattice problems
  • Existence of lattice problems that are as hard on average as on worst case (Ajtai, Regev, ...)
  • Existence of public key cryptosystems of security equivalent to the worst case complexity of a lattice problem (Ajtai-Dwork, Regev...)
• Interactive proofs with "efficient" prover (research project)
  • Consider the question of whether there can be an interactive proof for coNP where the prover can be implemented using a P^NP algorithm. Under what conditions can this be ruled out? It is related to the question of NP-complete problems having "instance checkers", "random-self-reducibilities" and "self-testers".
• Inapproximability results based on the "unique games conjecture"
  • Hardness of Vertex Cover within 2 and of k-uniform Hypergraph Vertex Cover within k
  • Hardness of Max CUT within .878... (with additional assumptions)
• Proof complexity
  • Lower bounds on resolution using width
  • Lower bounds on datalog programs to refute random instances of 3SAT
• Results in computational learning theory  (Sebastien)
  • Learning using  Fourier Analysis, harmonic sieve algorithm
• Lower bounds for monotone circuits
  • Razborov's lower bound for clique
  • The depth lower bound for st-connectivity
• Lower bounds in communication complexity
  • The Babai-Nisan-Szegedy "number on the forehead" model
• Lower bounds for algebraic circuits
  • Nisan's lower bound for non-commutative computations
  • Raz's lower bound for multilinear formulas (Project chosen by Satrajit)
  • Impagliazzo-Kabanets connection between algebraic complexity and derandomization of polynomial identity testing