Advanced Complexity Theory
Prof. Dr. Markus Bläser
- no lecture on Thu June 5 and 12
- lecture on Tue June 10 is from 10 to 12 in E1.3 HS3
TopicBeside 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
- Prof. Dr. Markus Bläser, Email: mblaeser at cs.uni-saarland...
Office Hours: whenever my office door is open, E 1 3, Room 412
PrerequesitesBasic knowledge in complexity theory
Oral exams at the end of the semester
- Sanjev Arora and Boaz Barak, Computational Complexity - A Modern Approach, Cambridge University Press.
- Oded Goldreich, Computational Complexity - A Conceptual Perspective, Cambridge University Press.