# Advanced Complexity Theory

## Prof. Dr. Markus Bläser

### News

- no lecture on Thu June 5 and 12
- lecture on Tue June 10 is from 10 to 12 in E1.3 HS3

### Topic

Beside the lecture notes, the following papers were treated in class:- Sebastien Tavenas: Reduction to depth four and three. pdf
- Ankit Gupta et al: Approaching the chasm at depth four. eccc
- Herve Fournier et al: Lower bounds for depth four circuits computing iterated matrix multiplication eccc
- Ankit Gupta et al: Chasm at depth three. eccc
- Dima Grigoriev and Marek Karpinski: An exponential lower bound for depth 3 arithmetic circuits. ps
- Mrinal Kumar and Shubhangi Saraf: Superpolynomial lower bounds for general homogeneous depth four circuits. eccc

### Time & Date

- Tue 12-14
- Thu 12-14
- E1.3 HS1 / HS 3

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

### Prerequesites

Basic knowledge in complexity theory### Grading

Oral exams at the end of the semester

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