T-79.300 Postgraduate Course in Theoretical Computer Science (2-10 cr)
Autumn 2004: Derandomization
Can everything, computable in BPP (randomized polynomial time), also be computed in P (deterministic polynomial time)? There are quite valid hypotheses and results showing that it can be done, under quite reasonable assumptions. Clearly, the result P=BPP would be very desirable from the practical viewpoint, enabling one to construct deterministic efficient algorithms for a large range of problems. Because of that, derandomization is currently one of the hottest topics in theoretical computer science. During this seminar, we plan to study up to the recent developments in this area. Our own motivation comes from the applicability of the derandomization results in cryptography, but people with different and diverse interest in other areas of computer science are more than welcome.
Registered students/personnel (contact us or register in webtopi if your name is not here): Phil Carmody, Tatiana Issaeva, Matti Järvisalo, Petteri Kaski, Alexey Kirichenko, Emilia Käsper, Sven Laur, Emilia Oikarinen, Pekka Orponen, Lauri Tarkkala, Alexey Vyskubov, Johan Wallén.
[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 22 January 2007. Helger Lipmaa