This is an old revision of the document!

Advanced Topics of Algorithmics: Complexity of Boolean Functions (MA-INF 1302)


Is P = NP? This is the most famous open problem in computer science. A popular approach to attack this problem is to look for a proof of a nonpolynomial lower bound for the circuit complexity of the characteristic function of a language in NP. But no nonlinear lower bound for such a function is known. Can we multiply two integers in linear time or can we prove an Ω(n log n) lower bound for the circuit complexity of the multiplication of two n-bit numbers? Understanding the power of negations is one of the most challenging problems of computer science. The main topic of this lecture is the development of techniques for proving lower bounds for the complexity of Boolean functions.


Art When Where Start Lecturer
V4 Monday 14:15 - 15:45
Wednesday 08:15 - 09:45
CP1-HSZ / Hörsaal 4
CP1-HSZ / Hörsaal 4
01. April 2019 Prof. Dr. N. Blum
Ü2 Wednesday 14:00 - 15:30 Room 2.074 10. April 2019 Schmitz

On the Wednesday, the 3rd of April, an additional lecture will be held between 12:15 and 13:45 in Room 2.050. Because of this, the lecture on the 24th of April will not be held.

Lecture Notes


Tutorial presence and exercise sheets are voluntary, but recommended. You can choose freely the tutorial group to participate and you do not have to hand in the solution of the exercise sheets. Also, there are no other requirements to take part in the oral examination as to register in BASIS.


Page Tools