Spring 2006 - Research laboratory in Foundations of Computer Science (236602)
Place: Taub 337
Sunday, 10:30-12:30
Course worksheets for all 14 sessions [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:
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 (60%) and homework (40%).
References
Proof Complexity
Propositional proof complexity: Past, Present and Future,
by
Beame, P., and Pitassi, T., In G. Paun, G. Rozenberg, and A. Salomaa,
editors. In
Current Trends in Theoretical Computer Science
Short Proofs are Narrow - Resolution made Simple, by Ben-Sasson, E. and Wigderson, A. In Journal of the ACM, March 2001, Vol. 48 No. 2.
Natural Proofs
Natural Proofs, by Razborov, A. A. and Rudich, S. , in Journal of Computer and System Sciences, Vol. 55, No 1, 1997, pages 24-35.
Fast Matrix Multiplication via Group Theory
A Group-theoretic Approach to Fast Matrix Multiplication, by H. Cohn and C. Umans, in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). pages 438-449. 2003.
Group-theoretic Algorithms for Matrix Multiplication, by H. Cohn, R. Kleinberg, B. Szegedy, and C. Umans, in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS). pages 379-388. 2005. Slightly more detailed 12 page version.
Primes is in P
PRIMES is in P, by M. Agrawal, N. Kayal and N. Saxena, Annals of Mathematics 160(2): 781-793, 2004.
Primality and Identity Testing via Chinese Remaindering, M. Agrawal and S. Biswas, Journal of the ACM 50(4): 429-443 (2003).