About the conference
History
In 1986 the first Structure in Complexity Theory Conference
was
organized with the support of the US National Science Foundation. As
indicated in the call for papers, the
conference focused on the global aspects of
computational complexity theory and the structural properties of both
complexity classes and complexity-bounded reducibilities
, and
became known as Structures
. From
1987 through 2014 the conference was sponsored by the
IEEE
Computer Society
Technical Committee
on Mathematical Foundations of Computing. In 1996 the conference
broadened its scope to the current one, and accordingly changed its name
to
Annual IEEE Conference on Computational Complexity
, abbreviated
as CCC
. In 2014, after a
community-wide discussion
and a strong
movement
towards independence based on a desire for open access to the
proceedings, the
Computational Complexity Foundation Inc. was
established. Starting from 2015 the Foundation organizes the
conference independently under the name
Computational Complexity Conference
,
maintaining the acronym CCC
.
The list of future and past conferences contains links to the websites for the individual years. Past programs and call for papers (going back to 1997) are also available there.
Scope
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.
Logistics
CCC is typically held sometime between mid-May and mid-July and somewhere in North America or Europe. The conference usually lasts three to three-and-a-half days with a relatively relaxed schedule. Papers are presented in a single track. There are also often invited speakers. Common evening activities include an opening reception, a rump session consisting of talks about recent breakthroughs and research in progress, and a business meeting that is open to all conference attendees.
Proceedings
Up to 2010 CCC had paper proceedings. Most of the historic proceedings are available in digital format, as indicated in the table below. Starting from 2015 the proceedings of CCC are published in the open access venue Leibniz International Proceedings in Informatics (LIPIcs).
| Years | Venue |
|---|---|
| 2015- | LIPIcs |
| 1996-2014 | IEEExplore and CSDL |
| 1995 | IEEExplore and CSDL |
| 1988-1994 | IEEExplore |
| 1986 | Springer LNCS |
Awards
CCC has a tradition of giving a Best Student Paper Award
for
the most outstanding paper written solely by one or more students.
As of 2015, funding for the best student paper award is provided by
the European Association for
Theoretical Computer Science (EATCS).
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.
As of 2014, based on an arrangement with the
Journal of the ACM,
authors of papers that receive the Best Paper Award are invited to
publish an extended version of the paper in that journal.
Special Journal 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). From 2004 till 2015, it appeared in the journal Computational Complexity (CC), and since 2016 in the open access journal Theory of Computing (ToC).