Applications du TCS aux mathématiques classiques?

En TCS, nous utilisons souvent des résultats et des idées puissants issus des mathématiques classiques (algèbre, topologie, analyse, géométrie, etc.).

Quels sont quelques exemples de quand il est allé dans le sens inverse?

Voici quelques exemples que je connaisse (et aussi pour donner une idée du type de résultats que je demande):

• Mousses cubiques (Guy Kindler, Ryan O'Donnell, Anup Rao et Avi Wigderson: Cubes sphériques et arrondis en grandes dimensions, FOCS 2008)
• Le programme de théorie de la complexité géométrique. (Bien qu'il s'agisse techniquement d'une application de la géométrie algébrique et de la théorie de la représentation au SDC, ils ont été amenés à introduire de nouveaux groupes quantiques et de nouvelles idées purement algébro-géométriques et théoriques de la représentation dans leur quête de P vs NP.)
• Travailler sur des intégrations métriques inspirées d'algorithmes d'approximation et de résultats inapproximables

Je ne cherche en particulier pas à appliquer les applications du TCS à la logique (théorie des modèles finis, théorie de la preuve, etc.) sauf si elles sont particulièrement surprenantes - la relation entre le TCS et la logique est trop étroite, standard et historique pour les besoins de cette question.

Les expandeurs ont été développés en grande partie dans TCS et ils ont de profondes connexions et applications aux mathématiques.

Il existe une preuve de Dvir de la conjecture de Kakeya à corps fini.

Je connais un exemple intéressant dans l'article de Michael Freedman intitulé " Complexity Classes as Mathematical Axioms ", qui donne une implication de dans le domaine de la topologie à 3 variétés.$P^{\sharp P}\neq NP$

Les principes d'invariance ont été motivés par la dureté de l'approximation, mais sont des théorèmes analytiques utiles. Le principe: une fonction de degré faible, dans laquelle chacune des variables a une faible influence, se comporte presque de la même manière, que les entrées soient des variables aléatoires indépendantes ou des variables aléatoires gaussiennes (correspondantes). C'est une généralisation du théorème de la limite centrale; la fonction est la moyenne des variables.

Stabilité au bruit des fonctions à faible influence: invariance et optimalité E. Mossel, R. O'Donnell, K. Oleszkiewicz. Annals of Mathematics 171 (1), p. 295-341 (2010). FOCS '05.

Les théorèmes de test à faible degré ont été motivés par les applications PCP, mais sont des théorèmes algébriques intéressants. Le principe: une fonction de variable sur un corps fini qui, en moyenne sur les lignes de , est proche de la distance de Hamming à un polynôme de degré faible sur la ligne , est proche de la distance de Hamming à un polynôme de degré faible l'ensemble .F F n F $n$$F$$F^n$$F^n$

La proximité de Hamming avec un polynôme de degré faible dans un certain espace signifie que la fonction s'identifie avec un polynôme de degré faible sur une fraction non négligeable de l'espace.

Amélioration des tests à faible degré et de ses applications . S. Arora et M. Sudan. Dans ACM STOC 1997.

Test de probabilité faible et de degré d'erreur sous-constante et caractérisation PCP de NP par une probabilité d'erreur et sous-constante , R.Raz, S.Safra, Compte rendu du 29ème STOC, 1997, p. 475-484

Bien que je sois partial, je pense qu’il est juste de dire que diverses idées du SDC ont contribué à faire avancer la conjecture inverse pour la norme de Gowers, voir par exemple le document de Green et Tao .

La théorie de la calculabilité fait-elle partie de TCS? Si tel est le cas, la théorie de la calculabilité et la géométrie différentielle de Bob Soare, qui expose les applications des résultats obtenus avec Csima, en sont un exemple.

Je ne sais pas pourquoi le lien n'apparaît pas .... Ici: http://www.people.cs.uchicago.edu/~soare/res/Geometry/geom.pdf

Extractors est un autre endroit à regarder. Par exemple, l'article de Barak-Kindler-Shaltiel-Sudakov-Wigderson'04 donne (entre autres choses) des constructions améliorées des graphes de Ramsey (un problème qui était ouvert depuis un moment en calcul discret).

De Wolf et Drucker mentionnent dans leur enquête sur les preuves quantiques le lien surprenant entre la complexité des requêtes quantiques et l’ approximation des fonctions symétriques par les polynômes.$\epsilon$

La construction en expandeur de Zig-Zag a été utilisée pour construire divers exemples intéressants de groupes avec certaines propriétés inattendues, voir Meshulam-Wigderson , Rozenman-Shalev-Wigderson . La construction elle-même est très intéressante d'un point de vue purement mathématique, car elle utilisait des outils complètement différents (motivés par le point de vue de la gestion de l'entropie) pour construire des expandeurs par rapport aux constructions précédentes. (Cependant, l'application la plus célèbre se trouve peut-être à l'intérieur de l'algorithme logspace de TCS- Reingold pour la connectivité non dirigée .)

Permettez-moi de mentionner quelques applications supplémentaires:

La contribution la plus importante du SDC aux mathématiques pures est peut-être l'art de la réduction. Les réductions de la forme utilisée par le SDC dans la complexité de calcul et d'autres endroits représentent un paradigme / outil mathématique qui est plus développé dans le SDC par rapport à d'autres domaines des mathématiques.

La notion de preuve probabiliste: Ici, je ne fais pas référence à la méthode probabiliste (qui a ses racines dans les mathématiques mais a de nombreuses applications en CS), mais plutôt au fait qu'un énoncé mathématique comme celui qui dit un certain nombre est un nombre premier, peut recevoir une preuve "hors de tout doute raisonnable". C’est une avancée conceptuelle venant de CS, même s’il n’avait pas encore beaucoup d’applications dans la façon dont les mathématiques sont pratiquées.

La preuve constructive de Moser du lemme local de Lovasz utilise des idées en informatique, donne une nouvelle preuve du lemme de Lovasz local et résout un problème auquel les gens pensent depuis un certain temps.

La méthode de la fonction de barrière de Batson-Spielman-Srivastava a eu de nombreuses applications en géométrie et en analyse fonctionnelle, est apparue en informatique, et constitue une forme très originale d'argument de fonction potentielle, rappelant la méthode des estimateurs pessimistes. De plus, il va à l’encontre de la croyance conventionnelle voulant que l’analyse du polynôme caractéristique des matrices aléatoires soit intraitable et qu’il vaut mieux regarder plutôt les moments matriciels.

La méthode de la fonction barrière a d'abord été développée pour prouver l'existence de sparsifiers (et de construire en temps polynomial déterministe) de graphes préservant leurs propriétés spectrales. Ces applications étaient motivées par des applications algorithmiques: essentiellement, tout algorithme devant calculer approximativement les réductions peut être accéléré en donnant en entrée une version fragmentée de l'entrée d'origine.

Au-delà des agents de scellement, la méthode a eu de nombreuses applications, dont beaucoup sont étudiées par Assaf Naor dans le présent document . Quelques exemples notables sont la construction de graphes d’agrandissement pondérés, les décompositions approximatives de l’identité avec moins de points, la réduction de la dimension des sous-espaces / sous-espaces de , une version rapprochée du principe d’inversibilité restreinte de Bourgain et Tzafriri. Pour toutes les applications ci-dessus, la méthode de la fonction barrière produit des limites essentiellement strictes, fournit un algorithme déterministe efficace en plus de la preuve d'existence, et fournit souvent une preuve plus élémentaire que les méthodes précédentes (bien qu'avec certains calculs compliqués).$\ell_1^n$

En 2013, Marcus, Srivastava et Spielman ont eu recours à la méthode de la fonction barrière, utilisant des stéroïdes et complétée par la machinerie des polynômes entrelacés , pour résoudre l'un des problèmes les plus notoires de l'analyse fonctionnelle, le problème de Kadison-Singer. . Ce problème découle de questions fondamentales en physique mathématique, mais il va beaucoup plus loin - il est connu pour être équivalent à des dizaines de problèmes partout en mathématiques. Sans oublier que de nombreux analystes (y compris Kadison et Singer) ne pensaient même pas que le problème avait une résolution positive (l’enquête citée de Cassaza et autres spécule sur des contre-exemples possibles).

Un exemple qui me vient à l’esprit est le théorème d’incorporation de Higman et ses conséquences théoriques de groupe.

Théorème de Higman sur l'incorporation: un groupe G est généré avec une présentation récursive si et seulement si et seulement si G est un sous-groupe d'un groupe présenté avec finalité.

(Notez que la partie gauche de l'équivalence a une composante de calcul, tandis que la droite est purement théorique.)

La signification de l’ aléatoire , ce que l’on qualifie de "séquence aléatoire" et les questions connexes étaient importantes en mathématiques, en théorie des probabilités et en statistique pendant des siècles. L'informatique théorique (et la théorie de la complexité) offrent des informations très robustes, profondes et convaincantes, permettant de comprendre le caractère aléatoire.

Alors que la méthode probabiliste mise en place en mathématiques, la dérandomisation, qui est un concept mathématique important, est principalement développée en CS.

Ceci est lié à la réponse de Moritz .

Théorie des automates et algèbre

La théorie des automates a donné des résultats intéressants pour caractériser l'algèbre. J'en mentionne deux, avec des références. Ce n'est en aucun cas exhaustif.

1. Une fermeture algébrique de$\mathbb F_q(t)$

Soit le champ de la fonction rationnelle sur le corps fini avec éléments, où pour certains premiers et entiers . Soit l’anneau des séries formelles de pouvoir sur .qq= p s ps F q [[t]] F$\mathbb F_q(t)$$q$$q=p^s$$p$$s$$\mathbb F_q[[t]]$$\mathbb F_q$

On peut caractériser les séries de puissances algébriques sur$\mathbb F_q(t)$ , c'est-à-dire les racines d'un polynôme monique à coefficients dans , en utilisant une description de la théorie des automates.$\mathbb F_q(t)$

$\sum_{i=0}^{\infty} a_i t^i$$\mathbb F_q(t)$$\{a_i\}_{i=0}^\infty$$p$

$\mathbb F_q(t)$

$\sum_{i\in I} a_i t^i$$\mathbb F_q(t)$$\{a_i\}_{i\in I}$$p$

2. Nombres transcendantaux

Les séquences automatiques sont également utilisées pour caractériser les nombres transcendantaux. Par exemple,

$b$$\ge 2$$x\in\mathbb R$$\mathbf x=\{x_i\}_{i=0}^\infty$$b$

1. $\mathbf x$$x$
2. $\mathbf x$$b$$x$
3. $x$

Bien sûr, le premier élément est un résultat très classique!

Références.

[1] Gilles Christol. Ensembles presque périodiques k-reconnaissables . Dans Theoretical Computer Science 9 (1), pages 141-145, 1979.

[2] Kiran S. Kedlaya. Automates finis et extensions algébriques des champs de fonctions . Dans le Journal de théorie des nombres de Bordeaux 18 , pages 379 à 420, 2006. arXiv: math / 0410375 .

[3] Boris Adamcweski, Yann Bugeaud. Sur la complexité des nombres algébriques I. Expansions en bases entières . Dans Annals of Mathematics 165 (2), pp 547-565, 2007.

$L$$\tau$

$L$

$\tau$$p$$\tau$$(1+\tau)^c$$c$

IMHO TCS est une branche des mathématiques et je le dirais un peu plus large. Nous vivons à l'ère de l'algorithmique, presque tout le monde, dans toutes les activités humaines, invente / réinvente les algorithmes, principalement l'heuristique. Mais certains de ces algorithmes sont 1. bons; 2. contiennent (enterrés) des réponses à des questions mathématiques profondes; 3. Attendez une analyse / amélioration / attention mathématique professionnelle. Mon expérience personnelle: la puissance saisissante d’une heuristique physique / apprentissage automatique, à savoir l’approximation de Bethe, en tant que technique de preuve. Le principal problème est que de telles rencontres possibles se produisent principalement dans l'industrie, où personne ne se soucie de ces informations / révélations non liées aux produits.