Gems of theoretical Computer Science (G53GEM) - Autumn 2003

Convenors

Natasha Alechina
Thorsten Altenkirch,

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).

Links


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