Computational Complexity Conference

La conférence Computational Complexity Conference (abrégé en CCC) est une conférence scientifique annuelle dans le domaine de l'informatique théorique, dont les origines remontent à 1986[1]. Elle a pour thème principal la recherche en théorie de la complexité au sens informatique du terme. La conférence a lieu en général entre la mi-mai et la mi-juillet habituellement, mais pas seulement, en Amérique du Nord. Auparavant organisée sous les auspices de l'IEEE, elle est, depuis 2015, organisée de façon indépendante par une fondation spécifique, la Computational Complexity Foundation (CCF)[2], en coopération avec l'European Association for Theoretical Computer Science (EATCS) et le Special Interest Group on Algorithms and Computation Theory (SIGACT) de l’ACM. Les conférences sont sponsorisées par Microsoft Research et par l'EATCS.

Computational Complexity Conference (CCC)

Type	Conférence académique
Création	1986
Localisation	villes variées en Amérique du Nord et en Europe
Date	annuelle
Site web	http://www.math.utu.fi/projects/dlt/

Historique

CCC a eu lieu la première fois en 1986 sous le nom Structure in Complexity Theory Conference, avec le support de la National Science Foundation[1]. De 1987 à 2014, la conférence a été sponsorisée par le Technical Committee on Mathematical Foundations of Computing de la IEEE Computer Society. En 1996, la conférence change de nom et devient la Annual IEEE Conference on Computational Complexity ; l'acronyme « CCC » date de cette époque. En 2014, un mouvement vers plus d'indépendance et le souhait d'avoir des actes en libre accès conduisent à l’établissement de la Computational Complexity Foundation (CCF)[2].

Depuis 2015, CCF organise la conférence indépendamment sous le nom de Computational Complexity Conference (CCC), et publie les actes en libre accès via la série LIPIcs[3]. Les actes des colloques précédents sont disponibles sur IEEE Xplore et IEEE Computer Society Digital Library — CSDL pour les années 1995-2014, sur IEEE Xplore seule de 1988 à 1994, et dans les Springer LNCS pour l'année1986.

Thèmes de la conférence

CCC a pour thème la théorie de la complexité en informatique théorique dans le sens le plus large. Ceci comprend notamment l'étude de modèles de calcul, tant déterministes que quantique, ou algébrique, autant que l'influence des contraintes en ressources. Les contraintes typiques en ressources peuvent être le temps, l'espace, l'aspect probabiliste, la taille des logiciels, les requêtes d'entrée, la communication et l'interaction; l'évaluation dans le pire des cas, ainsi que le cas moyen. d'autres sujets plus spécifiques, notamment les systèmes de preuve probabiliste et interactive, inapproximabilité, la complexité, la preuve de la complexité descriptive, et les aspects de la complexité de la théorie de la cryptographie et l'apprentissage de la machine.

Organisation

Comme il est usuel dans ce type de conférences, les contributions sont évaluées par des pairs. CCC a lieu chaque année entre mi-mai et mi-juillet, avec un programme scientifique de trois jours environ. La conférence n'a pas de sessions parallèles. Deux prix sont décernés : un « Best Student Paper Award » à partir de 2015 et un « Best Paper Award » à partir de 2001.

Chaque année un petit nombre de présentations sont invités par le comité de programme à soumettre des versions complètes à un numéro spécial d'une revue. Les communications passent par le processus normal de l'arbitrage de la revue, mais apparaissent souvent plus tôt que si elles avaient été soumises de la manière habituelle. Depuis la création de la conférence en 1986 et jusqu'en 2003, un numéro spécial de la revue Journal of Computer and System Sciences (JCSS) est consacré à ces articles, à l'exception de 1990, où il est paru dans Theoretical Computer Science (TCS). De 2004 à 2015, c'est un numéro de la revue Computational Complexity (CC), et depuis 2016 dans la revue en libre accès Theory of Computing (ToC).

Impact

À titre d'illustration, le comité de programme de la 31^e conférence (CCC’16) a retenu 34 communications parmi les 91 soumissions, après avis de plus d'une centaine de rapporteurs externes ; ceci qui donne un taux d'acceptation de 37 % environ.

Conférences précédentes ou à venir

Les conférences précédentes ou à venir sont[4] :

33^e Conference on Computational Complexity, 20-22 juin 2018, San Diego (Californie)
32^e Conference on Computational Complexity, 6-9 juillet 2017, Riga (Lettonie)
31^e Conference on Computational Complexity, 29 mai - 1^er juin 2016, Tokyo (Japon)
29^e IEEE Conference on Computational Complexity, 11-13 juin 2015, Vancouver (British Columbia)

...

11^e IEEE Conference on Computational Complexity, 24-27 mai 1996, Philadelphie (Pennsylvanie)
10^e Structure in Complexity Theory Conference, 19-22 juin 1995, Minneapolis (Minnesota)
9^e Structure in Complexity Theory Conference, 28 juin - 1^er juillet 1994, Amsterdam (Pays-Bas)

...

2^e Structure in Complexity Theory Conference, 16-19 juin 1985 Ithaca (New York)
1^re Structure in Complexity Theory Conference, 2-5 juin 1986, Berkeley (Californie).

Références

Organisation générale CCC
Site de la Computational Complexity Foundation (CCF)
Leibniz International Proceedings in Informatics (LIPIcs)
[référence, citation ou lien]http://computationalcomplexity.org/conferences.php Liste des conférences