FOCS 2006
47th Annual IEEE Symposium on
Foundations of Computer Science

October 22-24, 2006
Doubletree Hotel, Berkeley, CA

Main Page
Hotel Reservations
Accepted Papers
Instructions for Authors
Call for Papers
Visa Info
Travel info
Berkeley, CA
Organizing team

47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006)

Berkeley, CA
October 22-24, 2006

The 47th Annual Symposium on Foundations of Computer Science (FOCS 2006), sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, will be held in Berkeley, CA, October 22-24, 2006. Papers presenting new and original research on theory of computation are sought. Typical but not exclusive topics of interest include: algorithms and data structures, computational complexity, cryptography, computational geometry, computational game theory, algorithmic graph theory and combinatorics, randomness in computing, parallel and distributed computing, machine learning, applications of logic, algorithmic algebra and coding theory, theoretical aspects of databases, information retrieval, networks, computational biology, robotics, and quantum computing. More information on the conference is available on the FOCS 2006 web site:

Important Dates:


Submission deadline:

Paper must be received by Tuesday April 11, 2006 (16:59 EDT) or postmarked by March 30, 2006.


Accept/reject decisions will be made by June 26, 2006.

Final versions:

Final versions of accepted papers due Aug 11, 2006.

Abstract format:

Authors should submit an extended abstract (not a full paper). The submission should contain a scholarly exposition of ideas, techniques, and results, including motivation and a clear comparison with related work. The length should not exceed ten (10) letter-sized pages (not including the bibliography and figures) using 11-point or larger font, with ample spacing and margins all around. More details may be given in an appendix, but any material beyond the 10-page limit may be ignored at the discretion of the Program Committee. Abstracts deviating significantly from these guidelines risk rejection without consideration of their merits.

Abstract submission:

Authors are strongly encouraged to submit their extended abstracts electronically. The electronic submission site will be here. Authors who are unable to submit electronically must send twenty three (23) printed copies (double-sided preferred) of an extended abstract, together with a cover letter, to:

Sanjeev Arora
FOCS 2006 Program Chair
Dept. of Computer Science
Princeton University, 
35 Olden St,

Princeton, NJ 08540

To facilitate notification, authors submitting printed copies should also send an e-mail, to , indicating that they are submitting in this manner. The abstract, in either form, MUST be received by 16:59 EDT April 11, 2006 or postmarked by March 30, 2006. Late submissions will be rejected. Simultaneous submission of the same (or essentially the same) abstract to FOCS and to another conference with published proceedings is not allowed.


Authors will be sent notification of acceptance or rejection by e-mail on or before June 24, 2006. A final copy of each accepted paper is required by Aug 5, 2006. Again this is a firm deadline. An author of each accepted paper must attend the symposium and present the paper, or make alternative arrangements to have it presented.


Machtey award:

This prize will be given to the best paper written solely by one or more students. An abstract is eligible if all authors are full-time students at the time of submission. This should be indicated through the electronic submission process or by email to the program chair. The program committee may decline to make the award, or may split it among several papers.


Program Committee:


  • Rajeev Alur, University of Pennsylvania
  • Matthew Andrews, Lucent Bell Laboratories
  • Sanjeev Arora, Princeton University (Chair)
  • Avrim Blum, CMU
  • Moses S. Charikar, Princeton University
  • Shuchi Chawla, University of Wisconsin, Madison
  • Jeff Erickson, University of Illinois, Urbana-Champaign
  • Lisa K. Fleischer, IBM Watson
  • Lance Fortnow, University of Chicago
  • Ravi Kannan, Yale University
  • Sampath Kannan, University of Pennsylvania
  • Haim Kaplan, Tel-Aviv University
  • Anna Karlin, University of Washington
  • Joe Kilian, Rutgers University
  • Guy Kindler, Microsoft Research
  • Ashwin Nayak, University of Waterloo
  • Christos Papadimitriou, UC Berkeley
  • Harald Raecke, TTI Chicago
  • Rajmohan Rajaraman, Northeastern University
  • Dana Randall, Georgia Tech
  • Michael Saks, Rutgers University
  • Daniel A. Spielman, Yale University
  • Peter Winkler, Dartmouth College

Information about local arrangements can be obtained from the Local Arrangements Web page at or from the Local Arrangements Chair:

Satish Rao
Computer Science Division
681 Soda Hall
University of California
Berkeley, CA 94720-1776