Thorsten Altenkirch,

The module involves discussing chapters from the book by U. Schoening and R. J. Pruim "Gems of Theoretical Computer Science" (Springer, 1998). Each week, a student (or a group of students) will make a one hour presentation on one of the chapters of the book followed by discussion. The student(s) will meet with a member of staff to discuss and plan the form of the presentation. The student(s) should also prepare some questions for the audience and write a concise (10 pages) summary of the chapter.

The name in brackets indicates the consultant for that chapter.

- 9.10.
- Spectral Problems and Descriptive Complexity Theory (chapter 7)
*Natasha* - 16.10.
- Hilbert's Tenth Problem (chapter 2)
*Thorsten* - 30.10.
- The equivalence problem for LOOP(1)-and LOOP(2)-programs. (chapter 3)
*Hussein Jodiyawalla (Natasha)* - 6.11.
- PAC-Learning and Occam's Razor (chapter 10)
*James Aldred (Thorsten)* - 13.11.
- The Pebble Game (chapter 24)
*Mark Shropshall (Natasha)* - 20.11
- Quantum Search Algorithms (chapter 26)
*Chris Kasprowicz (Thorsten)* - 27.11.
- Exponential Lower Bounds for the Length of Resolution Proofs (chapter 6)
*Morgan Evans(Natasha)* - 4.12.
- LOGSPACE, random walks on graphs and universal traversal sequences (chapter 5)
*Lloyd Colling (Thorsten)* - 5.12.
- The priority method (Chapter 1)

*Jon Masters (Thorsten)*

Below are the titles of the chapters of the book - each corresponds to a potential seminar presentation. Only a few of them will be covered this year (not necessarily in this order).

- The Priority Method
- Hilbert's Tenth Problem
- The Equivalence Problem for LOOP(1)- and LOOP(2)-Programs
- The Second LBA Problem
- LOGSPACE, Random Walks on Graphs, and Universal Traversal Sequences
- Exponential Lower Bounds for the Length of Resolution Proofs
- Spectral Problems and Descriptive Complexity Theory
- Kolmogorov Complexity, the Universal Distribution, and Worst-Case vs. Average-Case
- Lower Bounds via Kolmogorov Complexity
- PAC-Learning and Occam's Razor
- Lower Bounds for the Parity Function
- The Parity Function Again
- The Complexity of Craig Interpolants
- Equivalence Problems and Lower Bounds for Branching Programs
- The Berman-Hartmanis Conjecture and Sparse Sets
- Collapsing Hierarchies
- Probabilistic Algorithms, Probability Amplification, and the Recycling of Random Numbers
- The BP-Operator and Graph Isomorphism
- The BP-Operator and the Power of Counting Classes
- Interactive Proofs and Zero Knowledge
- IP = PSPACE
- P does not equal NP with probability 1
- Superconcentrators and the Marriage Theorem
- The Pebble Game
- Average-Case Complexity
- Quantum Search Algorithms

- Gems of Theoretical Computer Science - Information about the book.
- Module description

Thorsten Altenkirch Last modified: Tue Oct 22 13:52:37 BST 2002