|
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
|
