Computational Complexity Conference: Difference between revisions

Revision as of 23:24, 4 April 2017

Latest revision as of 06:40, 21 February 2025

(29 intermediate revisions by 11 users not shown)

Line 1:

{{Short description|Academic conference in computer science}}

{{Userspace draft|source=ArticleWizard|date=July 2016}}

{{refimprove|date=August 2024}}

{{use dmy dates|date=August 2024}}

The '''Computational Complexity ConferencConference''' ('''CCC'''), is an [[academic conference]] in the field of [[theoretical computer science]] whose roots date to 1986 .<ref name="CCCgeneral">[{{Cite web |url=http://computationalcomplexity.org/general.html |title=General Info, CCC web page] |access-date=5 April 2017|archive-url=https://web.archive.org/web/20170405170132/http://computationalcomplexity.org/general.html |archive-date=5 April 2017 |url-status=dead }}</ref>. It fosters research in "all areas of [[computational complexity theory, studying the absolute and relative power of computational models under resource constraints"]], and is typically held annually between mid-May and mid-July in North America or Europe. As ofSince 2015, CCC ishas been organized independently by the [http://computationalcomplexity.org/foundation/ Computational Complexity Foundation (CCF)], which provides open access to the proceedings.

== History ==

InCCC was first organized in 1986 under the firstname "Structure in Complexity Theory Conference" was organized(Structures) with the support offrom the [[US National Science Foundation]].<ref As indicated in the [http://computationalcomplexity.org/first-cfp.pdf call for papers], the conference focused name="on the global aspects of computational complexity theory and the structural properties of both complexity classes and complexity-bounded reducibilitiesCCCgeneral", and/> became known as "Structures". From 1987 through 2014 theThe conference was sponsored by the [httphttps://web.archive.org/web/20160412120153/https://www.computer.org/portal/web/guest/hometcmf IEEE Computer Society Technical Committee on Mathematical Foundations of Computing] from 1987 to 2014. In 1996, the conference broadenedwas its scope torenamed the current one, and accordingly changed its name to "Annual IEEE Conference on Computational Complexity", abbreviatedthus asestablishing the current acronym "CCC". In 2014, after a strong [http://computationalcomplexity.org/letter-of-support.php movement towards independence] basedand onopen aaccess desireproceedings for open accessled to the proceedings,establishment of the CCF.<ref>[http://computationalcomplexity.org/foundation/ Computational Complexity Foundation Inc.(CCF)]</ref> was established. Starting fromSince 2015, theCCF Foundationhas organizesorganized the conference independently under the name "Computational Complexity Conference", maintaining the acronym CCC, and publishes itsopen access proceedings invia theLeibniz openInternational accessProceedings venuein Informatics.<ref>[http://www.dagstuhl.de/en/publications/lipics Leibniz International Proceedings in Informatics (LIPIcs)]</ref> Future and past conference websites, as well as past programs and call for papers, are archived online.

In 1986 the first "Structure in Complexity Theory Conference" was organized with the support of the US National Science Foundation. As indicated in the [http://computationalcomplexity.org/first-cfp.pdf 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 [http://www.computer.org/portal/web/guest/home 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 strong [http://computationalcomplexity.org/letter-of-support.php movement towards independence] based on a desire for open access to the proceedings, the [http://computationalcomplexity.org/foundation 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, and publishes its proceedings in the open access venue [http://www.dagstuhl.de/en/publications/lipics Leibniz International Proceedings in Informatics (LIPIcs)].

Future and past conference websites, as well as past programs and call for papers (going back to 1997), are archived [http://computationalcomplexity.org/conferences.php online].

CCC was first organized in 1986 under the name "Structure in Complexity Theory Conference" (Structures) with support from the US National Science Foundation. Initially, it centered on the "global aspects of computational complexity theory and the structural properties of both complexity classes and complexity-bounded reducibilities",<ref name="CCCgeneral" /> eventually broadening its scope in 1996 to "all areas of computational complexity theory, studying the absolute and relative power of computational models under resource constraints".<ref name="CCCgeneral" /> From 1987 to 2014, CCC was sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, during which time it was known as the IEEE Conference on Computational Complexity. In 2014, a movement towards independence and open access proceedings led to the establishment of the Computational Complexity Foundation (CCF), which renamed the conference the Computational Complexity Conference <ref name="CCF">[http://computationalcomplexity.org/foundation/ Computational Complexity Foundation (CCF)]</ref>. Since 2015, CCC has been organized independently by CCF, and publishes open access proceedings via LIPIcs.<ref name="LIPIcs" />

== Scope ==

CCC broadly targets research in computational complexity theory. This currently{{when|date=August 2024}} includes(but is not limited to the study of models of computation ranging from deterministic to quantum to algebraic, as well as resource constraints such as time, randomness and input queries.

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 held annually between mid-May and mid-July, with a scientific program running for approximately three days. The conference is composed of a single-track. Activities in addition to the scientific program typically include an opening reception, a rump session and a business meeting.

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.

== Awards ==

CCC annually confers up to two awards: a "Best Student Paper Award", aimed at papers authored solely by students and, since 2001, a "Best Paper Award", given to the most outstanding paper at the year's conference.

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 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.

CCC annually confers up to two awards: A "Best Student Paper Award", aimed at papers authored solely by students, and (since 2001) a "Best Paper Award", given to the most outstanding paper at the respective year's conference. Funding for the former is provided (since 2015) by the European Association for Theoretical Computer Science (EATCS).<ref name="EATCS">[http://www.eatcs.org/ European Association for Theoretical Computer Science (EATCS)]</ref> As of 2014, recipients of the Best Paper Award are invited to publish in the Journal of the ACM.<ref name="JACM">[http://jacm.acm.org/ Journal of the ACM]</ref>

== References ==

Line 29 ⟶ 20:

== External links ==

* [http://computationalcomplexity.org/ Computational Complexity Conference (CCC) web page [http://computationalcomplexity.org/]

* Computational Complexity Foundation (CCF) web page [http://computationalcomplexity.org/foundation/ Computational Complexity Foundation web page]

{{Authority control}}

[[Category:Theoretical computer science conferences]]