
Lecturer:
Prof. Dr. Ernst W. Mayr


Area:
2 lectures per week in
area III (Theoretical Computer Science)
advanced course
, topic complexity


Time and Place:
Thu 8:30  10:00, lecture hall 1180
Start: 5. November


Exercises:
2 hours per week exercises accompanying the lectures
Wed 8:30  10:00, room S2225
Start: 11. November
Teaching Assistant: Volker Heun
Course Certificate: To get a course certificate students must
get at least 40% on the homework assignments and
pass the final exam.


Audience:
graduate students of computer science
students with computer science as minor


Prerequisites:
Course Complexity Theory advantageous, but not necessary.


Recommended for:
Indepth knowledge in topic Complexity


Contents:
An interesting and challenging areo of algorithm theory
are lower bounds for the time or space complexity of problems.
In this course,
several known techniques for proving lower bounds will
be presented and illustrated by examples.
 Introducion and Overview
 Goals of this Lecture
 References
 Techniques for Lower bounds
 Models of Computation
 Basic definitions and Notations
 Space and Time Bounds for Turing Machines
 A Quadratic Time Bound for 1Tape Turing Machines
 A GapTheorem for Small Deterministic Space
 A GapTheorem for 1Tape Turing Machines
 Hierarchies
 General Hierarchy Theorems
 Time Hierarchies
 Space Hierarchy
 Nondeterministic Hierarchy Theorems
 Space vs. Time
 1Tape Turing Machines
 A Pebble Game
 Construction of Computation Graphs
 Boolesche Circuits
 Basic definitions and Notations
 Asymptotic Bounds
 Probabilistic Methods
 The Class AC_{0}
 Small Depth Circuits for Parity
 Håstad's Lower Bound
 An exponential Lower Bound for Parity
 An algebraic Method (Razborov)
 Summary


Related and Advanced Lectures:
Complexity Theory


Lecture Notes:
Not available.


References:

K.R. Reischuk:

Einfhrung in die Komplexittstheorie
B.G. Teubner, 1990

J. HÔstad:

Computational limitations of smalldepth circuits
The MIT Press: Cambridge(MA)London, 1987


Office Hours:
look here
