**
Spring 2009 - Research laboratory in Foundations of Computer Science
(236610)**

**
Place: Taub **

Monday, **
10:30-12:30**

**
Course worksheets [PDF,
postscript].**

Come and 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.

The main topic for this sememster is Additive Combinatorics and its applications to Computer Science. Tentative list of results to be studied

- Roth's Theorem about the existence of arithmetic progressions of length 3 in dense subsets of finite additive groups.
- The Gowers norm and Samorodnitsky's Theorem about testing quadratic functions over small finite fields.
- The Bogdanov-Viola pseudorandom generator for low-degree polynomials.
- Sum-product theorems in finite fields and extractors for independent sources.

The course is of theoretical nature and assumes mathematical maturity. It is especially recommended for students who have successfully took the Complexity Theory class (236313), but this is not a formal prerequisite.

Final grade based on participation in class (30%) homework (40%) and final project (30%).

**References appear in scribe notes**