IEEE Conference on
Computational Complexity

The 24th Conference

July 15th to July 18th, 2009

Paris, France

This site was replaced on December 12th, 2008!  Please see the new site at computationalcomplexity.org.

Announcements

The 2009 call for papers is now available.

A vote on special issues journals was taken at the 2008 business meeting.  This page contains information about that vote. 

Please look here for the 2008 conference program, local arrangements web site, and the list of accepted papers. 

The 2009 conference will be held from July 15th to July 18th in Paris's historic Latin Quarter.  A preliminary local arrangements site is available.  See below for visa information.  

The 2010 conference will be in Boston on dates to be determined and co-located with STOC 2010. 

Purpose and Scope

This is an annual conference that deals with computational complexity broadly defined. It is usually held sometime between mid-May and mid-July and somewhere in North America or Europe.  A call-for-papers is issued each summer by August 1st.  Among the topics considered in the scope of the conference are:

• Complexity classes
• Algebraic complexity
• Proof complexity
• Interactive and probabilistic proof systems
• Circuits complexity
• Kolmogorov complexity
• Reducibility and completeness
• Communication complexity
• Inapproximability
• Cryptographic complexity
• Complexity and learning
• Complexity and logic
• Quantum computation
• Average case complexity
• Pseudorandomness and derandomization
• Complexity in other concrete computational models

This conference is sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing. The conference is overseen by a conference committee. Each year a program committee selects papers to be presented at the conference.

The previous web site for the conference was maintained by Luc Longpre, the immediate past publicity chair. 

Recent Meetings

• The 23rd meeting, June 22nd to June 26th, 2008, College Park, Maryland
  • List of accepted papers (HTML)
  • Conference schedule (HTML)
  • Call for papers (PDF)
  • Local arrangements web site
• The 22nd meeting, June 12th to June 16th, 2007, San Diego, California
  • List of accepted papers (HTML)
  • Conference schedule (HTML)
  • Call for papers (HTML)
  • FCRC local arrangements web site
• The 21st meeting, July 16th to July 20th, 2006, Prague, Czech Republic
  • List of accepted papers (HTML)
  • Conference program (PDF)
  • Call for papers (HTML)
  • Local arrangements web site
• The 20th meeting, June 12th to June 15th, 2005, San Jose, California
  • List of accepted papers (HTML)
  • Conference program (HTML)
  • Call for papers (HTML)
  • Local arrangements web site
• The 19th meeting, June 21st to June 24th, 2004; Amherst MA
  • List of accepted papers (HTML)
  • Conference program (HTML)
  • Call for papers (PDF, Postscript, DVI, HTML )
  • Local arrangements web site
  • On-line proceedings
• The 18th meeting, July 7th to July 10th, 2003; Århus, Denmark  
  • List of accepted papers (HTML)
  • Conference program (PDF, PostScript )
  • Schedule for the Kolmogorov Day (Sunday, July 6th, 2003)
  • Call for papers (PDF, Postscript, DVI, HTML )
  • Local arrangements web site
  • On-line proceedings
• The 17th meeting, May 21st to May 24th, 2002; Montréal, Québec  
  • Local arrangements web site
  • On-line proceedings

On-line published work on computational complexity

The IEEE has posted many of the articles from the proceedings of the third through tenth conferences (1988 to 1995) and from the proceedings of the eleventh through twenty-second conferences (1996 to 2007).  There are bibliographies for all but the 2nd and 3rd conferences at the DBLP site of the University of Trier. 

Other places to find published work on computational complexity include:

• The Electronic Colloquium on Computational Complexity at the University of Trier 
• The Computing Research Repository (CoRR)
• The Networked Computer Science Technical Reference Library (NCSTRL)
• The journal Computational Complexity

Other links of interest include:

• IEEE Computer Society
• Technical Committee on Mathematical Foundations of Computing
• The Computational Complexity Weblog

Miscellaneous documents

Calls for papers and other documents from the past few conferences are available above.   

The conference charter (PDF and Microsoft Word format) was voted on and approved at the business meeting of the 2002 conference in Montréal.

For many years the conference issued a booklet of research abstracts which were available electronically a week before the conference.  This practice has been discontinued because so much current work is now available on the Internet.  For the last few years, Steve Fenner created the booklet and he still maintains the abstracts web site, where one can download past years' booklets. 

Visa processing

The 2009 conference will be held in France.  A visa to France is waived in many cases, including for citizens of the countries of the Schengen Agreement, United States, Canada, Israel, and Japan.  However, it is mandatory in other cases, for example, for citizens of mainland China and India. Please visit this web site for all the necessary information. If a visa is needed, we recommend that people get in touch with their local French consulate as soon as possible to see what the local procedure is.
 

This website is maintained by John Rogers, School of Computing, DePaul University
Last update: Friday, December 12th, 2008. This page will not be updated again. It has been superceded by the new site.