Computational Complexity

Publications

Teaching

Workshops

# Complexity Theory

## Karteek Sreenivasaiah PhD

### News

• Room for the reexam is 007 in the bioinformatics building.
• There will be a tutorial on Wednesday Oct. 7, at 11:15 (room E1.3, 415) for re-exam preparation.
• If you would like to take the re-exam, please send an email to Markus Bläser.

### Topic

Complexity Theory is the science of classifying and sorting computational problems by its inherent difficulty.

### Time & Date

• Mi 8:30 - 10:00, E1.3, HS1
• Fr 10:15 - 11:55, E1.3, HS1
Tutorial:
• Friday 8-10, E1.3, SR16
• Tutor: Fabian Wobito, s9fawobi@stud...
• You can put your solutions in box 35 in E 2 5.

### Lecturer

• Prof. Dr. Markus Bläser, Email: mblaeser at cs.uni-saarland...
Office Hours: whenever my office door is open, E 1 3, Room 412
• Dr. Holger Dell, Email: hdell@mmci...
Office Hours: whenever my door is open, E1.3, room 414
• Karteek Sreenivasaiah PhD, Email: karteek@mpi-inf.mpg.de
Office Hours: whenever my door is open, E1.3, room 422

### Prerequesites

• "Grundzüge der theoretischen Informatik" or something equivalent is helpful

Exam dates:
• End of term: Fri Aug 7, 9 -12, seminar room 14, E1.3
• Re-exam: Fri Oct 9, 9 - 12, room 007, bioinformatics building
• There will be no midterm
To be admitted to the exams, you need 50% of points that can be achieved in the assignments.

• 36 points = 100%,
• 33 points = 90% = 1.3 (1.0 starts with 35 points)
• 29 points = 80% = 2.3 (30,31 = 2.0, 32 = 1.7)
• 23.5 points = 65% = 3.3 (25,26 = 3.0, 27, 28, = 2.7)
• 18 points = 50% = 4.0 (minimum pass mark) (22,23 = 3.7)
Endterm results:
• 2542800, 40 points, 1.0
• 2536656, 35 points, 1.0
• 2550610, 33 points, 1.3
• 2549796, 33 points, 1.3
• 2543779, 24 points, 3.3
• 2519577, 18 points, 4.0
• 2557952, 11 points, 5.0

Re-exam results:

• 2549796, 31 points, no improvement
• 2550610, 24 points, no improvement
• 2557952, 17 points, 4.0

### Literature

There are many good books on this topic. Here is a small selection

• Sanjev Arora and Boaz Barak, Computational Complexity - A Modern Approach, Cambridge University Press.
• Oded Goldreich, Computational Complexity - A Conceptual Perspective, Cambridge University Press.