Trabalho de Graduação --- Provas Interativas com Conhecimento Zero

• Aluno: Tiago Vignatti
• Monografia: .pdf.gz
• Conteúdo: Classes de complexidade P, NP, BPP, PSPACE; Classes de complexidade IP, PZK; Exemplos
• Objetivos: Entender os fundamentos e as aplicações de sistemas de provas iterativas
• Carga horária: 120+120 Créditos: 8+8
• Prof Responsável: Jair
• Bibliografia:
  1. Oded Goldreich.
     Foundations of cryptography.
     Cambridge University Press, Cambridge, 2001.
     Basic tools.
  2. Oded Goldreich, Silvio Micali, and Avi Wigderson.
     Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, volume 38.
     ACM Press, New York, NY, USA, 1991.
  3. S Goldwasser, S Micali, and C Rackoff.
     The knowledge complexity of interactive proof-systems.
     In STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing, pages 291-304, New York, NY, USA, 1985. ACM Press.
  4. Shafi Goldwasser and Mihir Bellare.
     Lecture notes on cryptography.
     Summer Course ``Cryptography and Computer Security'' at MIT, 1996-1999, 1999.
  5. Yoshiharu Kohayakawa and José Augusto Soares.
     Demonstração transparentes e a impossibilidade de aproximação.
     Editora do IMPA - Instituto de Matemática Pura e Aplicada, Rio de Janeiro - RJ, julho de 1995.
  6. Rajeev Motwani and Prabhakar Raghavan.
     Randomized algorithms.
     Cambridge University Press, Cambridge, 1995.
  7. Christos M. Papadimitriou.
     Computational complexity.
     Addison-Wesley, Reading, Massachusetts, 1994.
  8. Adi Shamir.
     IP=PSPACE.
     volume 39, pages 869-877, 1992.
  9. Michael Sipser.
     Introduction to the theory of computation.
     PWS Publishing Company, 1997.