Bibliography

 

Books and Lecture-notes

 

[Hagg]          Olle Haggstrom.      Finite Markov Chains and Algorithmic Applications.

[G-Lecture]   Oded Goldreich.     Introduction to Complexity Theory – Lecture Notes.

[G-Modern]   Oded Goldreich.     Modern Cryptography, Probabilistic Proofs and Pseudo-randomness.

[G-Foundations]      Oded Goldreich.     Foundations of Crptography.

[K-Lecture]   Mauricio Karchmer.                    Advanced Complexity Theory. Lecture Notes 1990.

[MR]             Rajeev Motwani and Prabhakar Raghavan.       Randomized Algorithms.

[Pap]            Christos Papadimitriou.     Computational Complexity.        

 [Vad]           Salil Vadhan.                              A Study of Statistical Zero-Knowledge Proofs.

 

 

Papers

 

*      [GS] Shafi Goldwasser, Michael Sipser. Private Coins versus Public Coins in Interactive Proof Systems

*      [O] Ryan O’Donnell. Hardness Amplification Within NP.

*      R. Impagliazzo, A Personal View of Average-Case Complexity  

*      R. Impagliazzo, Hardcore Distributions for Somewhat Hard Problems  

*      Luca Trevisan.
Extractors and Pseudorandom Generators
J. of the ACM, 48(4):860-879, 2001
Preliminary version In Proc. of 31st ACM STOC, pp. 141-148, 1999.
[Full version (2/99, revised 5/00)][Conference Proceedings]

 

 

Surveys

 

*      Luca Trevisan
Some Applications of Coding Theory in Computational Complexity
Survey Paper
To appear in Quaderni di Matematica
Final version: [ps] [pdf]

*      Luca  Trevisan
Error-Correcting Codes and Pseudorandom Projections
Invited Talk
Abstract in Proc. of RANDOM-APPROX, pp. 7-9, 2001

*      Luca Trevisan
A Survey of Optimal PCP Characterizations of NP
Tutorial
Abstract in Proc. of 15th IEEE Conference on Computational Complexity (CCC'00), pp. 146-148, 2000

*      Luca  Trevisan.
Interactive and probabilistic proof-checking
Survey paper
In Annals of Pure and Applied Logic, 104:325-342, 2000
[Final version]

*      Andrea E.F. Clementi, Jose D.P. Rolim and Luca Trevisan.
Recent Advances Towards Proving P=BPP
Survey paper
Bulletin of the EATCS, 64:96-103, 1998.
[Final version]

*      V. Kabanets,        Derandomization: A Brief Overview. (updated 09/06/03)

 

 

Papers to present

 

*      V. Kabanets, Easiness Assumptions and Hardness Tests: Trading Time for Zero Error.

*      O. Goldreich, A. Wigderson. Derandomization that is Rarely Wrong from Short Advice that is Typically Good Randomization and Approximation Techniques in Computer Science, 6th International Workshop, RANDOM 2002, pp. 209-223, 2002

(Abstract) [ Draft of final version (postscript) ] [ Draft of final version (pdf) ] [bibTeX entry]

 

*      Luca Trevisan, Salil Vadhan and David Zuckerman
Compression of Samplable Sources
In Proc. of 19th Computational Complexity Conference, IEEE, 2004
[Conference Proceedings]

*      R. Impagliazzo and A. Wigderson
Randomness vs. Time: De-randomization under a uniform assumption

*      V. Kabanets and R. Impagliazzo, Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

*       [V] Emanuele Viola. Hardness vs. Randomness within Alternating Time

*      [HVV] Alex Healy, Salil Vadhan and Emanuele Viola. Using Nondeterminism to Amplify Hardness.

*      Steven Rudich and A. Razborov.  Natural Proofs

 

 

More papers

 

*      R. Impagliazzo and S. Rudich ,         Limits on the Provable Consequences of One-Way Permutations

*      R. Impagliazzo, R. Shaltiel and A. Wigderson        Near-Optimal conversion of Hardness into Pseudo-Randomness

*      R. Impagliazzo and A. Wigderson      P=BPP unless E has sub-exponential circuits: De-randomizing the XOR Lemma

*      Johan Håstad R. Impagliazzo, L. Levin, and Michael Luby
Construction of a pseudo-random generator from any one-way function.

*      Andrej Bogdanov and Luca Trevisan
On Worst-Case to Average-Case Reductions for NP Problems
In Proc. of 44th FOCS, IEEE, pp. 308-317, 2003
[Draft full version] [Conference Proceedings] 

*      Luca Trevisan
List Decoding Using the XOR Lemma
In Proc. of 44th FOCS, IEEE, pp. 126-135, 2003
[Conference Proceedings]

*      Luca Trevisan and Salil Vadhan
Pseudorandomness and Average-case Complexity via Uniform Reductions
In Proc. of 17th  Computational Complexity Conference, pages 129-138, IEEE, 2002
[Conference Proceedings]

*      Madhu Sudan, Luca Trevisan and Salil Vadhan.
Pseudorandom Generators Without the XOR Lemma
J. of Computer and System Sciences, 62(2):236-266, 2001
Preliminary version: Proc. of 31st ACM STOC,  1999.
[Draft full version][Conference Proceedings]

*      [BT] Andrej Bogdanov and Luca Trevisan. On Worst-Case to Average-Case Reductions for NP Problems