Algebraic complexity theory
Prof. Dr. Markus Bläser
TopicWe will try to understand recent developments in lower bounds for aritthmetic circuits, in particular current upper and lower bounds for depth-4 and depth-3 circuits.
Papers to read:
- Manindra Argawal, V Vinay: Arithmetic circuit: A chasm at depth four pdf
- Pascal Koiran: Arithmetic circuits: The chasm at depth four gets wider pdf
- Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi: Approaching the chasm at depth four pdf
- Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi: A chasm at depth three pdf
- P. Koiran. Valiant's model and the cost of computing integers. pdf
- P. Bürgisser: On defining integers and proving arithmetic circuit lower bounds pdf
Time & Date
- Prof. Dr. Markus Bläser, Email: mblaeser at cs.uni-saarland...
Office Hours: whenever my office door is open, E 1 3, Room 412