News
Currently, no news are available
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".