Below is a list of topics and papers. You need to read one paper from this list (or any related paper of your choice).  

Here is a short-list that could be more useful. I think papers  1, 3, 4, 5, 10 are probably the most self-contained ones and possibly 2, 8, 9 as well.

  1. Decoding Reed-Solomon code beyond the Error-correction diameter. by Madhu Sudan
  2. Trevisan's extractor. Extractors and Pseudorandom Generators  L Trevisan
  3. Hardness versus Randomness.  Nisan-Wigderson.
  4. Lower bounds for AC_0 using Håstad's Switching Lemma. J. Håstad, Almost Optimal Lower Bounds for Small Depth Circuits.
  5. Lower bounds for monotone circuits. Lower bounds for the monotone complexity of some Boolean function . A. Razborov.
  6. New simpler proof of PCP Theorem by Irit Dinur
  7. Lattice problems in NP intersect coNP, Oded Regev and Dorit Aharonov
  8. J. Kahn, M. Saks, and D. Sturtevant. A topological approach to evasiveness. Combinatorica, 4:297--306, 1984.
  9. Pseudorandom Generator for Space Bounded Computation by N. Nisan
  10. Klim Efremenko:  3-Query Locally Decodable Codes of Subexponential Length
  11. Reingold's proof showing that  UNDIRECTED-ST-CONNECTIVITY  is in L .

 

 



List Decoding of Reed Solomon Codes:
  1. Decoding Reed-Solomon code beyond the Error-correction diameter. by Madhu Sudan
  2. Improved decoding of Reed-Solomon and algebraic-geometry codes (Madhu Sudan and Venkatesan Guruswami)
  3. Survey by Madhu Sudan List decoding: Algorithms and applications. and Course Notes
  4. Limits to list decoding assuming hardness of Discrete Log. On the list and bounded distance decodibility of Reed-Solomon codes.
    Qi Cheng and Daqing Wan. 


Applications of Coding Theory in Complexity:
  1. Some Applications of Coding Theory in Computational Complexity Survey by Luca Trevisan.
  2. Trevisan's extractor. Extractors and Pseudorandom Generators L Trevisan
  3. Pseudorandom generators without the XOR lemma (M. Sudan, L. Trevisan and S. Vadhan) 
Random self-reducibility:
  1. Random self reducibility for permanent, discrete log. On the Hardness of the PermanentD. Sivakumar, J. Cai and A. Pavan.
  2. On the random-self-reducibility of complete sets. L. Fortnow and J. Feigenbaum.
  3. On Worst-Case to Average-Case Reductions for NP Problems (L. Trevisan and A. Bogdanov) 




Derandomization of BPP under Hardness Assumptions:
  1. Hardness versus Randomness Nisan-Wigderson.
  2. P=BPP unless E has subexponential circuits: Derandomizing the XOR Lemma Impagliazzo-Wigderson
  3. Pseudorandom generators without the XOR lemma (M. Sudan, L. Trevisan and S. Vadhan)
  4. Derandomizing BPP - A survey ( Lecture notes ) by Avi Wigderson.




Derandomizing small space algorithms:
  1. Pseudorandom Generator for Space Bounded Computation by N. Nisan
  2. RL is contained in SC by N. Nisan.
  3. Algorithmic Derandomization via Complexity Theory by D. Sivakumar


Limited Independence and Derandomization :
  1. Pairwise Independence and Derandomization Survey by Luby and Wigderson.
  2. Simple constructions of almost k-wise independent random variables N. Alon, O. Goldreich, J. Hastad and R. Peralta.
  3. Small-Bias Probability Spaces: Efficient Constructions and Applications. Joseph Naor, Moni Naor.
  4. Algorithmic Derandomization via Complexity Theory by D. Sivakumar


Extractor/Expander Constructions:
  1. Trevisan's extractor. Extractors and Pseudorandom Generators L Trevisan
  2. Zig-zag expander construction O. Reingold, S. Vadhan, A. Wigderson. Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors.
  3. Nati Linal and Avi Wigderson's course on Expander Graphs and Their Applications.
  4. Tutorial given by Salil Vadhan at FOCS `02: Randomness Extractors and their Many Guises
  5. Reingold's proof showing that  UNDIRECTED-ST-CONNECTIVITY  is in L . 


Communication complexity : 

See the book by Nisan and Kushilevitz for background material.
  1. Information theory methods in communication complexity D. Sivakumar, Ziv Bar-Yossef, T.S. Jayram and S. Ravi Kumar.
  2. An information statistics approach to data stream and communication complexity D. Sivakumar, Ziv Bar-Yossef, T.S. Jayram, and Ravi Kumar
  3. Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Tradeoffs Laszlo Babai, Noam Nisan, Mario Szegedy. 


Circuit Lower Bounds using Communication Complexity:
  1. Chapters 10 and 11 of Kushilevitz Nisan.
  2. Approach to ACC^0 via number-on-forehead model (See Princeton notes lecture 20)
  3. Circuit Complexity and Communication Complexity lecture notes by Ran Raz
  4. Monotone Circuits for Matching Require Linear DepthR.Raz, A.Wigderson 


Circuit Lower bounds I:
  1. Lower bounds for AC_0 using Håstad's Switching Lemma. J. Håstad, Almost Optimal Lower Bounds for Small Depth Circuits.
  2. Lower bounds for monotone circuits. Lower bounds for the monotone complexity of some Boolean function . A. Razborov.
  3. Limits to current techniques. Natural Proofs A. Razborov and S. Rudich 


Circuit Lower Bounds II (Algebraic Methods):
  1. Algebraic methods in the theory of lower bounds for Boolean circuit complexity, by Roman Smolensky.
  2. Lower bounds for Montone Span Programs. Superpolynomial lower bounds for monotone span programs, by Laszlo Babai, Anna Gal and Avi Wigderson.
  3. Algebraic lower bounds for AC_0. The Expressive Power of Voting Polynomials by J. Aspnes, R. Beigel, M. Furst, and S. Rudich.

 

Decision tree complexity and evasiveness:
  1. H. Buhrman and R. de Wolf. Complexity Measures and Decision Tree Complexity: A Survey.
  2. Lecture notes on Evasivenss of Graph Properties L. Lovasz and N. Young.
  3. J. Kahn, M. Saks, and D. Sturtevant. A topological approach to evasiveness. Combinatorica, 4:297--306, 1984.
  4. Andrew Yao: Monotone Bipartite Graph Properties are Evasive. SIAM J. Comput. 17(3): 517-520 (1988 


Combinatorial Property Testing:
  1. O. Goldreich Combinatorial Property Testing -- A Survey
  2. O. Goldreich Short Locally Testable Codes and Proofs (survey) 
Complexity of Lattice Problems:  
  1. Lattice problems in NP intersect coNP, Oded Regev and Dorit Aharonov
  2. On the Limits of Non-Approximability of Lattice Problems O. Goldreich and S. Goldwasser
  3. Hardness of Approximating the Shortest Vector in a Lattice. Subhash Khot.
  4. Complexity of SVP---A reader's digest Ravi Kumar and D. Sivakumar 


Quantum Computing:
  1. Shor's algorithm, Grover's algorithm, Hidden subgroup problem. Umesh Vazirani's course on Quantum Computing,
  2. Ronald de Wolf. Quantum Communication and Complexity. Survey paper.
  3. Quantum Computation and Lattice Problems, Oded Regev. 


Foundations of Cryptography: 

See the book of the same name by Oded Goldreich. Any single chapter could be a reasonable project
  1. One-way functions
  2. Pseudorandom generators for cryptography
  3. Zero-knowledge Proofs. (advanced) 


PCPs and Hardness of Approximation:
  1. Proof of PCP Theorem. See Sanjeev Arora's thesis. 
  2. New simpler proof of PCP Theorem by Irit Dinur.
  3. Hardness results for various problems. Notes from the course on PCPs and Hardness of Approximation . (Mail Subhash for the complete set of notes).
  4. Inapproximability of Combinatorial Optimization Problems. Survey Paper by Luca Trevisan