Applications du TCS aux mathématiques classiques?

60

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.

Joshua Grochow
la source
1
C'est un peu difficile à répondre. La combinatoire est-elle en dehors des mathématiques classiques?
arnab
2
La combinatoire est certes une mathématique classique, mais je pense que le même commentaire s’applique à la combinatoire et à la logique. Ainsi, la conjecture de Kakeya à champ fini en est un bon exemple, alors que les nouvelles conceptions combinatoires motivées par les PRG sont davantage à la mode.
Joshua Grochow
Vous pouvez trouver de bons exemples en recherchant les résultats publiés, par exemple, dans Annals of Math par la communauté TCS.
HME

Réponses:

32

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

Gil Kalai
la source
22

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

Dai Le
la source
3
Cela était motivé par un problème d'extracteurs / fusions (voir le dernier article de Zeev et Avi Wigderson). D'autres améliorations (apportées par Madhu Sudan, Shubhangi Saraf, Swastik Kopparty et Zeev Dvir) ont utilisé davantage d'idées issues de l'informatique théorique, notamment du décodage par liste de codes (méthode de la multiplicité).
Dana Moshkovitz
1
Deux remarques: La méthode algébrique utilisée par Dvir est l’une des méthodes utilisées pour résoudre le problème classique des distances pour les ensembles planaires. terrytao.wordpress.com/2010/11/20/… et gilkalai.wordpress.com/2010/11/20/… .
Gil Kalai
2
Deuxièmement, les méthodes d'incidence et les résultats de la géométrie calculatoire et discrète avaient des applications antérieures pour le (vrai) problème de Kakeya.
Gil Kalai
20

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

Zeyu
la source
20

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 nnFFnFn

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

Dana Moshkovitz
la source
19

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 .

Manu
la source
7
De plus, il est juste de dire que les composantes de la preuve du théorème de Szemeredi à travers le lemme de régularité hypergraphique (de Gowers, Tao, Rodl, Schacht et autres) ont été influencées par le travail de Alon, Fischer, Shapira et d’autres lemme de régularité des graphes pour prouver la testabilité des propriétés des graphes.
arnab
18

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

Aaron Sterling
la source
2
Que vous considériez ou non la calculabilité dans le TCS, c’est un exemple que j’aime bien et que j’avais simplement oublié de mentionner. C'est encore plus cool parce que cela peut être fait en utilisant la complexité de Kolmogorov :).
Joshua Grochow
17

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

Moritz
la source
15

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

ilyaraz
la source
13

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

Boaz Barak
la source
10

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.

Gil Kalai
la source
1
Je ne savais pas que d'autres domaines des mathématiques utilisaient l'idée de réductions de manière significative. J'apprécierais vraiment toutes les références ou indications que vous pouvez donner à de telles œuvres! De plus, j'avais l'impression que les preuves probabilistes découlaient de la combinatoire pure et non du TCS?
Joshua Grochow
3
J'ai expliqué ce que je veux dire par "preuve probabiliste" dans la version modifiée de ma réponse. En ce qui concerne les réductions: La complexité informatique est un domaine des mathématiques enraciné en informatique. L'une des caractéristiques de ce domaine est l'utilisation de réductions qui jouent un rôle majeur sur les plans conceptuel et technique. Il est beaucoup plus développé que des techniques similaires dans d'autres domaines des mathématiques. Ainsi, l'art des réductions dans le SDC peut être considéré comme une application majeure du SDC aux mathématiques. Je pense que les réductions de type CS ont influencé les mathématiciens également dans d'autres domaines, et que d'autres sont à venir.
Gil Kalai
Joshua, laissez-moi vous donner une analogie. Supposons que quelqu'un se réfère au "calcul" comme l'une des plus grandes applications de la physique aux mathématiques classiques. On peut aussi dire que le calcul est principalement important pour s'attaquer à des problèmes de physique qui n'étaient pas auparavant "des mathématiques classiques". Néanmoins, je pense que le calcul est l’apport majeur de la physique aux mathématiques. De même, les réductions du type utilisé dans la théorie de la complexité constituent une contribution majeure du SDC aux mathématiques. Il décrit un appareil mathématique majeur et des idées mathématiques qui ont une valeur indépendante. (Pas aussi important que le calcul, cependant.)
Gil Kalai
@JoshuaGrochow Beaucoup de preuves commencent par quelque chose du type "On peut supposer que est connecté, car le nombre de widgets dans un graphique est la somme / le produit du nombre de widgets dans chaque composant", et souvent des versions plus sophistiquées de ce type de composants. idée. Cela compte-t-il comme une réduction du problème général au problème connecté? D'un autre côté, les mathématiciens le faisaient probablement bien avant que la théorie de la complexité informatique ne soit apparue. G
David Richerby
1
@JoshuaGrochow, il ne sera pas difficile de trouver des exemples non triviaux de "cas général aux réductions spéciales". Par exemple, l'enquête Cassaza que j'ai liée dans ma réponse présente des tonnes de réductions non négligeables entre des problèmes équivalents au problème de Kadison-Singer, dont certains sont très restreints à première vue. Je crois comprendre que la géométrie arithmétique regorge de telles choses, vous en saurez peut-être plus. Je ne sais pas dans quelle mesure le SDC peut se prévaloir d'avoir introduit cette approche pour résoudre des problèmes insolubles.
Sasho Nikolov
9

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.

Peter Shor
la source
9

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).1n

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

Sasho Nikolov
la source
5

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

microphone
la source
1
Ce lien a également été étendu à la complexité: la complexité temporelle non déterministe du problème de mot dans tout groupe est liée polynomialement à la plus petite fonction isopérimétrique (Dehn) de tout groupe présenté sous forme finie dans lequel peut être incorporé. En particulier, ssi peut être incorporé dans un groupe présenté finement avec au plus une fonction isopérimétrique polynomiale. Birget, Ol'shanksii, Rips et Sapir, Annals of Math. 2002 ams.org/mathscinet-getitem?mr=1933724H G W o r d ( G ) N P GGHGWord(G)NPG
Joshua Grochow
5

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 .

Gil Kalai
la source
5

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 deFq(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 qFq(t)qq=pspsFq[[t]]Fq

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

i=0aitiFq(t){ai}i=0p

Fq(t)

iIxiti,
IQFq(t)

iIaitiFq(t){ai}iIp

2. Nombres transcendantaux

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

b2xRx={xi}i=0b

  1. xx
  2. xbx
  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.

Bruno
la source
théorème (Adamczewski & Bugeaud [3]) peut être erroné ou mal compris
XL _At_Here_There
4

Lτ

L

τpτ(1+τ)cc

Bruno
la source
1

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.

gurvits leonid
la source