Seminář z výpočetní složitosti

Pavel Pudlák, Jiří Sgall

Předchozí program semináře, letní semestr 1999 [Previous program, Spring 1999]

20. 5., 27. 5. 1999

14.30

MÚ Žitná 25, 1. patro

Russell Impagliazzo and Avi Wigderson: Randomness vs. Time: De-randomization under a uniform assumption. In 39th Annual Symposium on Foundations of Computer Science, 1998.
(referuje P. Pudlák)

13. 5. 1999

14.30

MÚ Žitná 25, 1. patro

Luca Trevisan: Constructions of Near-Optimal Extractors Using Pseudo-Random Generators.
Electronic Colloquium on Computational Complexity, ECCC Report TR98-055, 1998
(referuje J. Sgall)

29. 4. 1999

14.30

MÚ Žitná 25, 1. patro

Madhu Sudan, Luca Trevisan, Salil Vadhan: Pseudorandom generators without the XOR Lemma.
Electronic Colloquium on Computational Complexity, ECCC Report TR98-074, 1998.
(referuje J. Sgall)

8. 4., 22.4. 1999

14.30

MÚ Žitná 25, 1. patro

Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 220-229, ACM, 1997.
(referuje D. Král a J. Sgall)

25. 3., 1.4. 1999

14.30

MÚ Žitná 25, 1. patro

Russell Impagliazzo. Hard-core distributions for somewhat hard problems.
In 36th Annual Symposium on Foundations of Computer Science, pages 538-545, IEEE, 1995.
(referuje P. Pudlák)

18. 3. 1999

14.30

MÚ Žitná 25, 1. patro

Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions.
In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 25-32, ACM, 1989.
(referuje P. Pudlák)

25. 2., 11.3. 1999

14.00

MÚ Žitná 25, 1. patro

Noam Nisan and Avi Wigderson: Hardness vs randomness.
Journal of Computer and System Sciences, 49(2):149-167, October 1994.
(referuje J. Sgall)

Jde o jeden ze zakladních článků o pseudonáhodných generátorech, jehož výsledky a techniky se využívají v dalších článcích, které budeme referovat.