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.

• Lattices - From cryptography and cryptanalysis to solving equations over the integers, lattices rule. Come see why. For a taste, go to Daniele Micciancio's introduction to lattices.

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