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

Summer term 2015


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.


Tue and Thu, 8-10h, LBH III.03a

Start of lecture:

Tue, 07.04.2015


Oral exams


Exercise Sheets

Lecture Notes:


In case of questions to the exercises, please contact Adrian Schmitz.