Note

Examination take place on February 13 and March 27. Send your preferred date to Matthias Fischer by  mafi(at)upb.de

Note:

The examinations are on 09.02. - 20.02. and 23.03. - 03.04. For registration use LSF (Master/Bachelor) or ZPS (DPO4)  [more].

Survey:

Complexity Theory deals with determining the amount of resources (e.g., runtime, memory consumption) necessary and sufficient for solving a given algorithmic problem (e.g. Travelling Salesperson Problem, TSP) on a given machine model (e.g., Turing machine).

One approach is to define complexity classes like P,NP, PSPACE, in order to classify problem complexity by means of completeness in such classes, like the famous class of NP-complete problems. This gives conditional results like ”If NP is not equal P, then TSP is not solvable in polynomial time.” This branch of Complexity Theory is often referred to as Structural Complexity Theory.

In contrast, proving explicit lower bounds for given problems is the topic of the so-called Concrete Complexity Theory. As nobody is currently able to prove superlinear time bounds for explicitly defined problems on general computation models like Turing machines, one considers somewhat restricted models like 1-tape Turing machines, monotone Boolean circuits, Boolean circuits with bounded depth, algebraic computation models, and several kinds of parallel computation models.

This lecture surveys approaches to prove such lower bound on various such models.

Topics:

• Boolean Circuits: basics, some lower bounds
• Algebraic computations: lower bounds for different sets of arithmetic operations
• Lower bounds for parallel computations

Lecture and Tutorials

Familiarity with basic concepts from complexity theory, as they are presented in the BA studies, are assumed.

The lecture and tutorials will be given in English.

• Lecture Friday, 14:15 - 16:00, F1.110, Friedhelm Meyer auf der Heide
• Tutorial I, Fr 13-14, F1.110, Daniel Warner

Homework will be available on Wednesday (morning), return is Wednesday until 4.00 pm.

Papers

• Lower Bounds For Algebraic Computation Trees, Michael Ben-Or
• Lower Bounds for Solving Linear Diophantine Equations on Random Access Machines, Friedhelm Meyer auf der Heide

More Lectures

• Concrete Models of Computation CS 497 JE: Spring 2003, Jeff Erickson. Especially the lectures from Febr 27, March 4.
• Lecture Notes of Uri Zwick

Examination

Oral examinations of 20 minutes duration. The exams will cover the lecture and also the tutorials and homework exercises.

Bonus Scheme

You can improve your grade by actively participating in the weekly tutorials and successfully solving the weekly homework exercises. For achieving at least 50 % of the total number of points in the homework exercises, your grade will improve by 1/3, for achieving at least 75 %, your grade will improve by 2/3. This only applies if you pass the examination.

Module Information

• Modules III.2.3, III. 2.4
• V2 + Ü1 SWS
• 4 ECTS credits (workload)

Literature

• Book: Complexity of Boolean Functions by Ingo Wegener.
• Script: Komplexitätstheorie II (german)