Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 Gems of theoretical Computer Science (G53GEM)
Gems of theoretical Computer Science (G53GEM) - Autumn 2003
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.
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