Spring 2008 - Research laboratory in Foundations of Computer Science (236602)

Place: Taub 8

Tuesday, 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.

 Tentative list of research questions for this semester

• New techniques for analyzing problems in communication complexity
• Applications of Additive Combinatorics in computer science
• Faster integer multiplication
• Study of the Unique Games Conjecture

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

See scribe notes