Fall 2006 - Research laboratory in Foundations of Computer Science (236602)
Time and place: Sunday, 10:30-12:30, Taub 6
Course worksheets for sessions 1-12 [PDF, postscript].
Experience research in foundations of computer science. Together we will study new research directions aimed at answering fundamental questions related to algorithms and computation. The course format will be self-study (during class hours) combined with short introductory lectures.
This semester we will focus on:
Locally testable error correcting codes - Can you check if a file of size 100 Megabyte contains no errors by reading only 10 bits of it? The answer is yes, as long as its encoded by a locally testable error correcting code. We will construct and analyze such codes.
The course is of theoretical nature and assumes mathematical maturity.
Final grade based on participation in class (30%), homework (40%) and final project (30%).
References appear in the course worksheets