|
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:
In-depth 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 1-Tape Turing Machines
- A Gap-Theorem for Small Deterministic Space
- A Gap-Theorem for 1-Tape Turing Machines
- Hierarchies
- General Hierarchy Theorems
- Time Hierarchies
- Space Hierarchy
- Nondeterministic Hierarchy Theorems
- Space vs. Time
- 1-Tape Turing Machines
- A Pebble Game
- Construction of Computation Graphs
- Boolesche Circuits
- Basic definitions and Notations
- Asymptotic Bounds
- Probabilistic Methods
- The Class AC0
- 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 small-depth circuits
The MIT Press: Cambridge(MA)-London, 1987
|
|
|
Office Hours:
look here
|
