News
No lecture on June 26!Written on 24.06.26 by Markus Bläser I am involved in Forschungstage Informatik and Anurag is attending a conference. Bad planning on our side. Sorry. Next lecture is July 03. |
Algebraic circuit lower bounds
In this lecture, we will study the complexity of computing polynomials. Our models of computation are algebraic, such as arithmetic formulas, algebraic branching programs, and general algebraic circuits. We will see how different structural restrictions on these models (like depth, monotonicity, or multilinearity) affect the ways we can analyze them. We will go over the classic methods used to prove lower bounds, review some of the most important results, and explain why proving strong lower bounds for general circuits is still one of the biggest open challenges in theoretical computer science.
Time and Date:
- Friday, 10:15 - 12:00, E1.3 HS001
- First lecture: Friday, April 10
This is an advanced lecture. There will be no tutorials.
.
Exams:
There will be oral exams at the end of the semester.
The exams can be at any time between the last week of the lecture period and end of October (provided that I am available).
Prerequisites:
"Grundzüge der Theoretischen Informatik" or equivalent (Introduction to computability and the theory of NP-completeness) is highly recommended. This course is self-contained and in particular, can be taken without having taken the core lecture "Complexity Theory".