Anwendungen von TCS in der klassischen Mathematik?

Wir in TCS verwenden häufig leistungsstarke Ergebnisse und Ideen aus der klassischen Mathematik (Algebra, Topologie, Analyse, Geometrie usw.).

Was sind einige Beispiele dafür, wann es umgekehrt gegangen ist?

Hier sind einige, die ich kenne (und die auch einen Vorgeschmack auf die Art der Ergebnisse geben sollen, nach denen ich frage):

• Würfelschäume (Guy Kindler, Ryan O'Donnell, Anup Rao und Avi Wigderson: Kugelförmige Würfel und Runden in hohen Dimensionen, FOCS 2008)
• Das geometrische Komplexitätstheorieprogramm. (Obwohl dies technisch eine Anwendung der algebraischen Geometrie und Darstellungstheorie auf das TCS ist, wurden sie veranlasst, neue Quantengruppen und neue rein algebro-geometrische und darstellungstheoretische Ideen bei der Verfolgung von P vs NP einzuführen.)
• Arbeiten Sie an metrischen Einbettungen, die von Approximationsalgorithmen und Unnäherungsergebnissen inspiriert sind

Insbesondere suche ich keine Anwendungen von TCS auf die Logik (Finite-Modell-Theorie, Beweis-Theorie usw.), es sei denn, sie sind besonders überraschend - die Beziehung zwischen TCS und Logik ist für die Zwecke dieser Frage zu eng und standardisiert und historisch.

Expander wurden größtenteils in TCS entwickelt und haben tiefe Verbindungen und Anwendungen zur Mathematik.

Es gibt Dvirs Beweis für die endliche Feld-Kakeya-Vermutung.

Ein nettes Beispiel, das ich kenne, ist Michael Freedmans Artikel mit dem Titel " Komplexitätsklassen als mathematische Axiome ", der eine Implikation von im Bereich der 3-Mannigfaltigkeitstopologie liefert.$P^{\sharp P}\neq NP$

Invarianzprinzipien wurden von der Härte der Approximation motiviert, sind aber nützliche analytische Theoreme. Das Prinzip: Eine Low-Degree-Funktion, bei der jede der Variablen einen geringen Einfluss hat, verhält sich nahezu gleich, egal ob es sich um unabhängige Zufallsvariablen oder um (entsprechende) Gaußsche Zufallsvariablen handelt. Dies ist eine Verallgemeinerung des zentralen Grenzwertsatzes; dort ist die Funktion der Durchschnitt der Variablen.

Rauschstabilität von Funktionen mit geringen Einflüssen: Invarianz und Optimalität E. Mossel, R. O'Donnell, K. Oleszkiewicz. Annals of Mathematics 171 (1), S. 295–341 (2010). FOCS '05.

Niedriggrad-Testsätze wurden von PCP-Anwendungen motiviert, sind jedoch interessante algebraische Sätze. Das Prinzip: Eine -Variatenfunktion über ein endliches Feld , die im Mittel über die Linien in in Hamming-Entfernung zu einem Polynom niedrigen Grades auf der Linie liegt , liegt in Hamming-Entfernung zu einem Polynom niedrigen Grades nahe an das ganze .F F n F $n$$F$$F^n$$F^n$

Die Nähe des Hamming-Abstands zu einem Polynom niedrigen Grades in einem bestimmten Raum bedeutet, dass sich die Funktion mit einem Polynom niedrigen Grades auf einem nicht zu vernachlässigenden Teil des Raumes identifiziert.

Verbesserte Low-Degree-Tests und ihre Anwendungen . S. Arora und M. Sudan. In ACM STOC 1997.

Ein Niedriggradtest mit subkonstanter Fehlerwahrscheinlichkeit und eine PCP-Charakterisierung mit subkonstanter Fehlerwahrscheinlichkeit von NP , R. Raz, S. Safra, Verfahren des 29. STOC, 1997, S. 475-484

Obwohl ich voreingenommen bin, ist es fair zu sagen, dass verschiedene Ideen von TCS dazu beigetragen haben, die inverse Vermutung für die Gowers-Norm voranzutreiben, siehe z. B. das Papier von Green und Tao .

Gehört die Berechenbarkeitstheorie zum TCS? Wenn ja, dann ist Computability Theory and Differential Geometry von Bob Soare ein Beispiel, das Anwendungen von Ergebnissen aufzeigt, die er mit Csima erhalten hat.

Ich weiß nicht, warum der Link nicht angezeigt wird. Hier: http://www.people.cs.uchicago.edu/~soare/res/Geometry/geom.pdf

Extraktoren ist ein weiterer Ort, um zu suchen. Die Arbeit von Barak-Kindler-Shaltiel-Sudakov-Wigderson'04 liefert unter anderem verbesserte Konstruktionen von Ramsey-Graphen (ein Problem, das in der diskreten Mathematik schon länger offen war).

$\epsilon$

Die Zick-Zack-Expander-Konstruktion wurde verwendet, um verschiedene interessante Beispiele für Gruppen mit bestimmten unerwarteten Eigenschaften zu konstruieren, siehe Meshulam-Wigderson , Rozenman-Shalev-Wigderson . Die Konstruktion selbst ist aus rein mathematischer Sicht sehr interessant, da sie völlig andere Werkzeuge (motiviert durch den CS-Gesichtspunkt des Umgangs mit Entropie) verwendete, um Expander als frühere Konstruktionen zu bauen. (Die vielleicht berühmteste Anwendung befindet sich jedoch in TCS- Reingolds Logspace-Algorithmus für ungerichtete Konnektivität .)

Lassen Sie mich noch ein paar Anwendungen erwähnen:

Der vielleicht wichtigste Beitrag von TCS zur reinen Mathematik ist die Kunst der Reduktion. Die Reduzierung der von TCS verwendeten Form in der Komplexität der Berechnungen und an anderen Stellen stellt ein mathematisches Paradigma / Werkzeug dar, das in TCS im Vergleich zu anderen Bereichen der Mathematik weiterentwickelt ist.

Der Begriff eines probabilistischen Beweises: Hier beziehe ich mich nicht auf die probabilistische Methode (die in der Mathematik verwurzelt ist, aber viele Anwendungen auf CS hat), sondern auf die Tatsache, dass eine mathematische Aussage wie die Aussage, die eine bestimmte Zahl beansprucht, eine Primzahl ist, kann einen Beweis erhalten "über jeden vernünftigen Zweifel hinaus". Es ist ein konzeptioneller Durchbruch von CS, obwohl es noch nicht viele Anwendungen in der Art und Weise gab, wie Mathematik praktiziert wird.

Mosers konstruktiver Beweis für das Lovasz Local Lemma basiert auf Ideen der Informatik, liefert einen neuen Beweis für das Lovasz Local Lemma und löst ein Problem, über das sich die Leute schon seit geraumer Zeit Gedanken gemacht haben.

Die Batson-Spielman-Srivastava- Barrierefunktionsmethode hat eine Reihe von Anwendungen für die Geometrie- und Funktionsanalyse, die in der Informatik entstanden sind, und ist eine sehr originelle Form eines möglichen Funktionsarguments, das an die Methode pessimistischer Schätzer erinnert. Darüber hinaus widerspricht es der gängigen Meinung, dass die Analyse des charakteristischen Polynoms von Zufallsmatrizen nicht möglich ist und man sich stattdessen besser mit Matrixmomenten befassen sollte.

Die Barrierefunktionsmethode wurde zuerst entwickelt, um die Existenz von (und die Konstruktion in deterministischer Polynomzeit) Sparsifiern von Graphen zu beweisen, die ihre spektralen Eigenschaften bewahren. Solche Sparsifier waren durch algorithmische Anwendungen motiviert: Im Wesentlichen kann jeder Algorithmus, der Schnitte ungefähr berechnen muss, beschleunigt werden, indem als Eingabe eine sparsifizierte Version der ursprünglichen Eingabe angegeben wird.

$\ell_1^n$

Marcus, Srivastava und Spielman verwendeten die Barriere-Funktionsmethode für Steroide, die mit der Maschinerie der Interlacing-Polynome erweitert wurde , um eines der bekanntesten Probleme in der Funktionsanalyse, das Kadison-Singer-Problem, zu lösen . Dieses Problem ergibt sich aus grundlegenden Fragen in der mathematischen Physik, aber es geht viel weiter - es bekannt ist, dass sie äquivalent zu Dutzenden von Problemen der ganzen Mathematik. Ganz zu schweigen davon, dass viele Analysten (einschließlich Kadison und Singer) nicht einmal der Meinung waren, dass das Problem eine positive Lösung hat (die zitierte Umfrage von Cassaza et al. Spekuliert über mögliche Gegenbeispiele).

Ein Beispiel, das mir in den Sinn kommt, ist der Einbettungssatz von Higman und seine gruppentheoretischen Konsequenzen.

Higmans Einbettungssatz: Eine Gruppe G wird endlich mit einer rekursiven Darstellung erzeugt, wenn G eine Untergruppe einer endlich dargestellten Gruppe ist.

(Beachten Sie, dass der linke Teil der Äquivalenz eine rechnerische Komponente hat, während der rechte Teil eine rein gruppentheoretische Komponente ist.)

Die Bedeutung von Zufälligkeit , was als "zufällige Folge" gilt und verwandte Fragen waren in Mathematik, Wahrscheinlichkeitstheorie und Statistik über Jahrhunderte wichtig. Die theoretische Informatik (und Komplexitätstheorie) bietet sehr solide tiefe und überzeugende Erkenntnisse für das Verständnis von Zufälligkeit.

Während die probabilistische Methode in der Mathematik begonnen hat, wird die Derandomisierung, die ein wichtiges mathematisches Konzept darstellt, hauptsächlich in der CS entwickelt.

Dies hängt mit Moritz 'Antwort zusammen.

Automatentheorie und Algebraizität

Die Automatentheorie lieferte einige interessante Ergebnisse zur Charakterisierung der Algebraizität. Ich erwähne zwei davon mit Referenzen. Es ist keineswegs erschöpfend.

$\mathbb F_q(t)$

$\mathbb F_q(t)$$q$$q=p^s$$p$$s$$\mathbb F_q[[t]]$$\mathbb F_q$

$\mathbb F_q(t)$$\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. Transzendentale Zahlen

Automatische Sequenzen werden auch verwendet, um transzendentale Zahlen zu charakterisieren. Zum Beispiel,

$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$

Natürlich ist der erste Artikel ein sehr klassisches Ergebnis!

Verweise.

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

[2] Kiran S. Kedlaya. Endliche Automaten und algebraische Erweiterungen von Funktionsfeldern . Im Journal de Théorie des Nombres de Bordeaux 18 , S. 379-420, 2006. arXiv: math / 0410375 .

[3] Boris Adamcweski, Yann Bugeaud. Zur Komplexität algebraischer Zahlen I. Erweiterungen in ganzzahligen Basen . In Annals of Mathematics 165 (2), S. 547–565, 2007.

$L$$\tau$

$L$

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

IMHO TCS ist ein Zweig der Mathematik und ich würde es etwas breiter ausdrücken. Wir leben im algorithmischen Zeitalter, fast jeder erfindet Algorithmen, hauptsächlich Heuristiken, in allen menschlichen Aktivitäten neu. Aber einige dieser Algorithmen sind 1. gut; 2. enthalten (begrabene) Antworten auf tiefe mathematische Fragen; 3. Warten Sie auf eine professionelle mathematische Analyse / Verbesserung / Aufmerksamkeit. Meine persönliche Erfahrung: eine erstaunliche Kraft einer Heuristik für Physik / maschinelles Lernen, nämlich die Bethe-Approximation, als Beweismethode. Das Hauptproblem besteht darin, dass mögliche Begegnungen dieser Art hauptsächlich in der Branche stattfinden, in der sich niemand um diese nicht produktbezogenen Erkenntnisse / Enthüllungen kümmert.