Department of Computer Science at the Technische Universität München
Chair for Efficient Algorithms
Postal address: 80290 München; Premises: Arcisstr.21, 80333 München

Lower Bounds (WS 98/99)

* 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