# Complexity Theory

## Prof. Dr. Markus Bläser

### News

Endterm is finally graded. I am sorry for the long delay.

- 2529826: 1.0
- 2551680: 1.0
- 2539243: 1.0
- 2551285: 1.3
- 2546548: 1.7
- 2546969: 2.0
- 2537067: 2.3
- 2528251: 2.7
- 2546809: 4.0
- 2526265: 4.0
- 2530382: 5.0

The reason for being so late is that we are organising a workshop on algebraic complexity theory next week. Attending the talks is free for local students nevertheless please register so that we know how much coffee we will need during the breaks.

### Time & Date

- Wed 10 - 12, E1.3 HS003
- Fri 12 - 14, E1.3 HS003
- First lecture Wed, Oct. 16

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

### Assistants

**Thatchaphol Saranurak**, Email: saranurak at cs.uni-saarland...

Office Hours: -, E1.3 Room 421

### Prerequesites

Grundzüge der Theoretischen Informatik (Introduction to Automata Theory, Computability, and Complexity) is quite helpful### Grading

50% Midterm + 50% Endterm or 100% Reexam

### Exam

Information for the endterm exam:- The midterm will take place Wednesday, Feb 26, 10:15 - 13:00.

Please be there in time! - You may bring one sheet of handwritten notes with you.

- Midterm:
**Dec. 18, 2013**, 10 - 12 (in the class room) at E1.3 HS 003 - Endterm:
**Feb. 26, 2014**, 10 - 13 at E1.3 HS 003 - Reexam:
**March 31, 2014**, 10 - 13 at E1.3 HS0 03

### Assignments

Tutorials are Fri 10-12 in E1.3, SR 016. First tutorial Nov 6.

- Assignment 1 (Hints)
- Assignment 10 (Hints)
- Assignment 11
- Assignment 2 (Hints)
- Assignment 3 (Hints)
- Assignment 4 (Hints)
- Assignment 5 (Hints)
- Assignment 6 (Hints)
- Assignment 7 (need not be handed in)
- Assignment 8 (Hints)
- Assignment 9 (Hints)

### Script

### Literature

- Sanjev Arora and Boaz Barak,
**Computational Complexity - A Modern Approach**, Cambridge University Press. - Oded Goldreich,
**Computational Complexity - A Conceptual Perspective**, Cambridge University Press. - V. Arvind and J. Torán,
**Isomorphism Testing: Perspectives and open problems**, Complexity theory column, in The Bulletin of EATCS number 86, June 200.