General Info

Topics

CCC aims to foster research in all areas of computational complexity theory, studying the absolute and relative power of computational models under resource constraints. Typical models include deterministic, nondeterministic, randomized, and quantum models; uniform and nonuniform models; Boolean, algebraic, and continuous models. Typical resource constraints involve time, space, randomness, program size, input queries, communication, and entanglement; worst-case as well as average case. Other, more specific, topics include: probabilistic and interactive proof systems, inapproximability, proof complexity, descriptive complexity, and complexity-theoretic aspects of cryptography and machine learning. The conference also encourages results from other areas of computer science and mathematics motivated by computational complexity theory.

Conference Meetings

CCC is held sometime between mid-May and mid-July and somewhere in North America or Europe. The conference usually lasts three and a half days with a relatively relaxed schedule. Papers are presented in a single track. There are also often invited speakers. Evening activities typically include a reception, a rump session consisting of talks about recent breakthroughs and research in progress, and a business meeting that is open to conference attendees.

Proceedings

IEEE posts the proceedings of the conference in both IEEExplore and CSDL. IEEExplore has the proceedings for the third through the tenth meeting (under the older name of "Structure in Complexity Theory Conference") and the eleventh through the current meeting. CSDL has the proceedings for the tenth meeting (under the name "Structure in Complexity Theory Conference") and the eleventh through the current meeting. There are bibliographies for all meetings at the DBLP site of the University of Trier.

Awards

The Ronald V. Book Prize for Best Student Paper is given to the most outstanding paper written solely by one or more students at the time of submission. The award is named after theoretical computer scientist Ronald Vernon Book (1937-1997). As of 2001, a Best Paper Award is given to the most outstanding paper submitted to the conference. For each award, the program committee may decide to split the award among two or more papers, or not to present the award at all.

Special Issues

Each year full versions of a small number of conference submissions are invited by the program committee to be submitted to a special issue of a journal. The submissions go through the normal journal refereeing process but will often appear sooner than if they had been submitted the usual way. From the conference's inception in 1986 to 2003 the special issue appeared in the Journal of Computer and System Sciences (JCSS), with the exception of 1990, when it appeared in the journal Theoretical Computer Science (TCS). Since 2004, it has appeared in the journal Computational Complexity (CC).