Lecture: Advanced Topics of Algorithmics: Complexity of Boolean Functions (MA-INF 1302)
Summer term 2015
Description:
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.
Lecture:
Tue and Thu, 8-10h, LBH III.03a
Start of lecture:
Tue, 07.04.2015
Exams:
Oral exams
Tutorials:
- Wed and Thu, 12:30-14h, II.57
Exercise Sheets
Lecture Notes:
Questions?
In case of questions to the exercises, please contact
Adrian Schmitz.