Some examples of research projects

• Interactive proofs with "efficient" prover 
  • 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".
• Algebraization
  • Aaronson and Wigderson have proposed the notion of algebraization; one drawback of the definition is that a proof that A is contained in B and that B is contained in C can both algebraize without immediately implying that A contained in C algebraizes. Can this ever happen? (Is there some, possibly contrived example, where A contained in B and B contained in C algebraize, but A contained in C does not?) Is there an alternative notion of relativization that does not suffer from this problem but within which one can prove that IP=PSPACE, but not that P!=NP?
• Average-case complexity of Random 3SAT
  • What kind of evidence can be found against random 3SAT being complete on average for NP? (Completeness against all samplable distribution under standard Levin-style reductions are easy to rule out, but what about more general reductions or more restricted classes of distributions?)