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 (čtvrtek [Thursday], 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 (čtvrtek [Thursday], 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 (čtvrtek [Thursday], 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 (čtvrtek [Thursday], 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 (čtvrtek [Thursday], 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 (čtvrtek [Thursday], 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 (čtvrtek [Thursday], 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.