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/ |
modifier ![]() |
Historique
modifierCCC 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
modifierCCC 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
modifierComme 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
modifierÀ titre d'illustration, le comité de programme de la 31e 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
modifierLes conférences précédentes ou à venir sont[4] :
- 33e Conference on Computational Complexity, 20-, San Diego (Californie)
- 32e Conference on Computational Complexity, 6-, Riga (Lettonie)
- 31e Conference on Computational Complexity, - , Tokyo (Japon)
- 29e IEEE Conference on Computational Complexity, 11-, Vancouver (British Columbia)
...
- 11e IEEE Conference on Computational Complexity, 24-, Philadelphie (Pennsylvanie)
- 10e Structure in Complexity Theory Conference, 19-, Minneapolis (Minnesota)
- 9e Structure in Complexity Theory Conference, - , Amsterdam (Pays-Bas)
...
- 2e Structure in Complexity Theory Conference, 16- Ithaca (New York)
- 1re Structure in Complexity Theory Conference, 2-, Berkeley (Californie).
Références
modifier- 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