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.

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

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

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