LEA
Department of Computer Science at the Technische Universität München
Chair for Efficient Algorithms
Postal address: 80290 München; Premises: Arcisstr.21, 80333 München
deutsch

Probabilistically Checkable Proofs (SS97)


* Lecturer:
Prof. Dr. Angelika Steger

* Area:
2 hours per week in area III (Theoretical Computer Science)
course admitted for examination

* Time and Place:
Wed 10:15 - 11:45, Room S2220
Start: May 7th

* Tutorials:
No Tutorials

* Audience:
3rd and 4th year students in computer science
3rd and 4th year students in mathematics with computer science as minor

* Prerequisites:
Basic knowledge in theoretical computer science

* Contents:
One of the recent spectacular highlights in theoretical computer science is a new characterization of the class NP in terms of probabilistically checkable proofs. This characterization has a fundamental impact on the classification of the approximability of combinatorial optimization problems. In this lecture the characterization as well as its implications will be presented.

* Lecture Notes:
Not available.

* References:
Journals and conference articles, references will be given during the course.

* Office Hours:
look here


steger@informatik.tu-muenchen.de