Principaux nouveaux articles sur la complexité informatique

Nous entendons souvent parler de recherches classiques et de publications dans le domaine de la complexité informatique (Turing, Cook, Karp, Hartmanis, Razborov, etc.). Je me demandais s'il y avait des articles récemment publiés considérés comme essentiels et à lire absolument. Récemment, je veux dire dans les 5/10 dernières années.

Le récent article de László Babai montrant que l’isomorphisme de graphes est en quasi-P est déjà un classique.

Voici une exposition plus accessible du résultat publié dans les actes de l'ICM 2018.

Dans une pré-impression récente, Harvey et Van Der Hoeven montrent comment calculer la multiplication d’Integer en temps $O(n \log n)$ sur une machine de Turing à bandes multiples, après 60 années de recherche (Karatsuba, Toom – Cook, Schönhage – Strassen, Fürer). , Harvey – Van Der Hoeven – Lecerf). Le document n'a pas encore été examiné par des pairs, mais les travaux antérieurs des auteurs sur ce problème le rendent plausible, et les experts semblent optimistes.

L'importance est dans les yeux du spectateur. Cependant, je dirais que la conjecture de dichotomie Feder – Vardi CSP, prouvée indépendamment par A. Bulatov et D. Zhuk , est un résultat déterminant.

Limites inférieures du circuit ACC non uniformes par Ryan Williams:

https://people.csail.mit.edu/rrw/acc-lbs.pdf

et vérification classique des calculs quantiques par Urmila Mahadev:

http://ieee-focs.org/FOCS-2018-Papers/pdfs/59f259.pdf

semble être de bons candidats

Ce nouvel article de Hao Huang [1] (à ce que je sache pas encore évalué par des pairs) qualifie probablement … il prouve l'hypothèse de sensibilité de Nisan et Szegedy, ouverte depuis environ 30 ans.

[1] Sous-graphiques induits d'hypercubes et preuve de la conjecture de sensibilité, Hao Huang. Manuscrit, 2019. https://arxiv.org/abs/1907.00847

Subhash Khot, Dor Minzer et le travail de 2018 de Muli Safra "Les ensembles pseudo-aléatoires dans Grassmann Graph ont une expansion quasi parfaite" nous ont permis de " nous mettre à mi-chemin" de la conjecture de Jeux uniques et est méthodologiquement assez intéressant selon des personnes plus informées que moi. Citant Boaz Barak ,

Ceci établit pour la première fois la dureté de jeux uniques dans le régime pour lequel un algorithme temporel sous-exponentiel était connu, et utilise donc (nécessairement) une réduction avec une certaine explosion polynomiale (importante). Bien qu’il soit théoriquement encore possible que la conjecture de jeux unique soit fausse (comme je le pensais personnellement jusqu’à cette dernière séquence de résultats), le scénario le plus probable est maintenant que le CGU est vrai et la complexité du , c) problème ressemble à ce qui suit ...

Le document a amené certains chercheurs (y compris Barak) à modifier publiquement leur opinion sur la vérité du CGU (de faux à vrai).

"Sur la possibilité d'algorithmes SAT plus rapides" de Pătraşcu & Williams (SODA 2010). Il établit des relations étroites entre la complexité de la résolution de CNF-SAT et la complexité de certains problèmes polynomiaux (ensemble k-dominant, somme d, etc.).

Les résultats sont doubles: soit nous pouvons améliorer la complexité de la résolution de certains problèmes polynomiaux. ETH est donc faux et nous obtenons un meilleur algorithme pour CNF-SAT. Ou bien l'ETH est vrai et nous obtenons ainsi des limites inférieures sur plusieurs problèmes polynomiaux.

Le papier est étonnamment facile à lire et à comprendre. Pour moi, c'est le début de la complexité fine.

Un an après la limite de 10 ans, mais «Déléguer le calcul: preuves interactives pour les moldus» de Goldwasser, Kalai et Rothblum a été un document extrêmement influent. Le résultat principal est qu'il existe une preuve interactive pour tout calcul uniforme log-space dans lequel le prouveur s'exécute dans le temps poly (n) et le vérificateur dans le temps n * polylog (n) avec des bits de communication polylog (n).

Le document a démarré la recherche sur les preuves interactives et le calcul vérifiable des problèmes en P a eu une influence incroyable sur la cryptographie, et les travaux qui ont suivi ont rendu les preuves interactives du monde réel presque pratiques.

Pour un impact, et atteindre le papier de référence par Indyk, et Backurs donnant des limites pour modifier le calcul de distance. Cet article montre les limites de l'informatique en liant k-SAT et SETH. Pour limiter le calcul de la distance entre les chaînes, le document indique des limites strictes pour le calcul de la distance de modification. Une violation supérieure à celle définie pour SETH est alors violée (SETH peut être faux en premier lieu, ou même avoir des limites inférieures plus étroites ). L'applicabilité de SETH à des problèmes éventuels dans P, pour obtenir des bornes ou pour limiter l'application d'algorithmes (éventuellement de calcul!) Est nouvelle.

Ou cet article de P. Goldberg et C. Papadimitrou, sur une complexité uniforme pour les fonctions totales Vers une théorie de la complexité unifiée des fonctions totales .

Je ne sais pas si cela remplit les conditions requises - il a plus de 10 ans, et ce n’est pas vraiment un résultat informatique complexe en soi - mais je pense que la paire de {Théorème de structure de graphe, Théorème de graphe mineur} mérite d’être soulignée. Il a été achevé en 2004 et établit une équivalence entre "complexité topologique bornée" et "ne contient pas un ensemble fini de mineurs". Chaque théorème établit une direction de l'équivalence.

Cela a principalement eu un impact dans le domaine de la théorie de la complexité paramétrée, où l'une de ces mesures est souvent liée, ce qui permet d'utiliser des algorithmes efficaces qui exploitent l'autre. Je dirais donc que ces résultats ont eu un impact considérable sur la complexité des calculs, même s'ils ne proviennent pas directement de ce domaine.