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