T-79.300 Postgraduate Course in Theoretical Computer Science (2-10 cr)

Autumn 2004: Derandomization

[Current] [General Information] [Schedule] [Arrangements]

Previous years: [Spring 2004] [Autumn 2003] [Spring 2003] [Autumn 2002] [Spring 2002] [Autumn 2001] [Spring 2001]

• Time: Wednesday 16-18 TB353. First seminar: 22.09.2004

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.

General

• Time, place: Wednesdays, 16:15 thru 18:00, seminar room TB353.
• Coordinator: Helger Lipmaa, room TB249.
• Registration by TOPI.
• Prerequisites: Basic knowledge of complexity theory, discrete mathematics and cryptography.
• Credits: Seminar presentation plus archivable slides plus oponing one presentation - 2 cr per topic. Presentation time: 1 hour.
  Extra credits: 4 pages own paper on seminar topic, related on the presentation: plus 1 cr. Other documented individual research additional 2 cr per topic.
  Active feedback from the audience is required after the presentation!

Schedule (continuously updated)

• 22.09 Course introduction. Objectives and structure of the seminar.
• 29.09 Extractors and Dispersers. (Alexey Vyskubov, based on Section 3 of Miltersen's book chapter + some parts of Section 4)
• 28.10 Extractors and Dispensers, II. (Alexey Vyskubov, Section 4.2)
• 03.11 Trevisan's extractor (Johan Wallen, Section 4.3)
• 10.11 HSGs and PRGs (Lauri Tarkkala, Section 5...)
• 17.11 Extractors from Reed-Muller Codes Sven Laur
• 24.11 Derandomization in Cryptology, Emilia Käsper

Arrangements

• Pointers to seminar material will be linked to the schedule above by coordinator.
• Electronic copy of presentation slides and/or seminar paper, together with any possible additional literature pointers mailed by presenter to coordinator by the presentation date. These will also be linked to the schedule above.
• Each speaker should discuss the material he/she intends to cover in his/her presentation with the coordinator ca. two weeks before the talk.

Seminar material (continuously updated)

• Helger Lipmaa's link collection at http://www.adastral.ucl.ac.uk/~helger/crypto/link/pseudorandom/derandomization.html, including: Miltersen's book chapter, Sahai's course material, and references therein, some newer papers.

Registered students

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.