Gems of theoretical Computer Science (G53GEM) - Autumn 2003

Convenors

Content

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.

Time table

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)

Topics

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

Links

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