Zastosowania TCS w matematyce klasycznej?

W TCS często używamy potężnych wyników i pomysłów z matematyki klasycznej (algebry, topologii, analizy, geometrii itp.).

Jakie są przykłady sytuacji, w której sytuacja się odwróciła?

Oto niektóre, o których wiem (a także, aby dać smak wyników, o które pytam):

• Sześcienne pianki (Guy Kindler, Ryan O'Donnell, Anup Rao i Avi Wigderson: Kuliste kostki i zaokrąglanie w dużych wymiarach, FOCS 2008)
• Program teorii złożoności geometrycznej. (Chociaż technicznie jest to zastosowanie geometrii algebraicznej i teorii reprezentacji w TCS, doprowadzono ich do wprowadzenia nowych grup kwantowych i nowych idei czysto algebro-geometrycznych i teorii reprezentacji w dążeniu do P vs NP.)
• Praca nad osadzaniem danych zainspirowanym algorytmami aproksymacji i wynikami niedopuszczalności

W szczególności nie szukam zastosowań TCS w logice (teoria modeli skończonych, teoria dowodów itp.), Chyba że są one szczególnie zaskakujące - związek między TCS a logiką jest zbyt bliski, standardowy i historyczny dla celów tego pytania.

Ekspandery zostały w dużej mierze opracowane w TCS i mają głębokie powiązania i zastosowania w matematyce.

Istnieje dowód Dvir na skończoną domysł Kakeya.

Ładny przykład, jaki znam, to artykuł Michaela Freedmana zatytułowany „ Klasy złożoności jako aksjomaty matematyczne ”, który daje implikację w dziedzinie 3-różnorodnej topologii.$P^{\sharp P}\neq NP$

Zasady niezmienności były motywowane twardością aproksymacji, ale są użytecznymi twierdzeniami analitycznymi. Zasada: funkcja niskiego stopnia, na którą każda ze zmiennych ma niewielki wpływ, zachowuje się prawie tak samo, bez względu na to, czy dane wejściowe są niezależnymi zmiennymi losowymi, czy (odpowiadającymi) zmiennymi losowymi Gaussa. Jest to uogólnienie centralnego twierdzenia o granicy; tam funkcją jest średnia zmiennych.

Stabilność hałasu funkcji o niskim wpływie: niezmienność i optymalność E. Mossel, R. O'Donnell, K. Oleszkiewicz. Annals of Mathematics 171 (1), s. 295–341 (2010). FOCS '05.

Twierdzenia o testach niskiego stopnia były motywowane aplikacjami PCP, ale są interesującymi twierdzeniami algebraicznymi. Zasada: Funkcja zmienna nad skończonym polem która średnio ponad liniami w , jest bliska w odległości Hamminga do wielomianu niskiego stopnia na linii , jest bliska w odległości Hamminga do wielomianu niskiego stopnia na cały .F F n F $n$$F$$F^n$$F^n$

Bliskość odległości Hamminga do wielomianu niskiego stopnia w pewnej przestrzeni oznacza, że ​​funkcja identyfikuje się z wielomianem niskiego stopnia na pewnej nieistotnej części przestrzeni.

Ulepszone testy niskiego stopnia i jego zastosowania . S. Arora i M. Sudan. W ACM STOC 1997.

Test niskiego stopnia prawdopodobieństwa błędu na stałym poziomie i charakterystyka prawdopodobieństwa błędu na stałym poziomie PCP dla NP , R.Raz, S.Safra, Proceeding of 29th STOC, 1997, str. 475-484

Chociaż jestem stronniczy, myślę, że można śmiało powiedzieć, że różne pomysły TCS przyczyniły się do postępu w odwrotnej domysłach dla normy Gowersa, patrz np. Artykuł Greena i Tao .

Czy teoria obliczalności jest częścią TCS? Jeśli tak, to Teoria Obliczeń i Geometria Różniczkowa Boba Soare'a, która eksponuje zastosowania wyników uzyskanych za pomocą Csima, jest przykładem.

Nie wiem, dlaczego link się nie wyświetla .... Tutaj: http://www.people.cs.uchicago.edu/~soare/res/Geometry/geom.pdf

Ekstraktory to kolejne miejsce do obejrzenia. Na przykład w pracy Baraka-Kindlera-Shaltiela-Sudakova-Wigdersona04 podano (między innymi) ulepszone konstrukcje grafów Ramseya (problem, który od pewnego czasu był otwarty w dyskretnych obliczeniach matematycznych).

De Wolf i Drucker wspomnieć w swoim badaniu dotyczącym kwantowej dowodów o zaskakującej połączenia między kwantowej złożoność zapytań i -approximation funkcji symetrycznych wielomianami.$\epsilon$

Konstrukcję ekspandera Zig-Zag zastosowano do konstruowania różnych interesujących przykładów grup o pewnych nieoczekiwanych właściwościach, patrz Meshulam-Wigderson , Rozenman-Shalev-Wigderson . Sama konstrukcja jest bardzo interesująca z czysto matematycznego punktu widzenia, ponieważ wykorzystywała zupełnie inne narzędzia (motywowane przez CS do radzenia sobie z entropią) do budowania ekspanderów niż poprzednie konstrukcje. (Jednak być może najbardziej znana aplikacja znajduje się w algorytmie przestrzeni logicznej TCS- Reingold dla nieukierunkowanej łączności ).

Pozwól mi wspomnieć o kilku innych aplikacjach:

Być może najważniejszym wkładem TCS w czystą matematykę jest sztuka redukcji. Redukcje formy stosowanej przez TCS w złożoności obliczeniowej i innych miejscach stanowią matematyczny paradygmat / narzędzie, które jest bardziej rozwinięte w TCS w porównaniu do innych obszarów matematyki.

Pojęcie dowodu probabilistycznego: nie odnoszę się tu do metody probabilistycznej (która jest zakorzeniona w matematyce, ale ma wiele zastosowań w CS), ale raczej do faktu, że wyrażenie matematyczne, takie jak stwierdzenie określające określoną liczbę, jest liczbą pierwszą, może otrzymać dowód „ponad wszelką uzasadnioną wątpliwość”. Jest to koncepcyjny przełom pochodzący z CS, chociaż nie miał jeszcze wielu zastosowań w praktyce matematyki.

Konstruktywny dowód Mosera na miejscową lematę Mosera wykorzystuje pomysły informatyczne, daje nowy dowód na lematę lokalną Lovasz i rozwiązuje problem, o którym ludzie myślą od dłuższego czasu.

Batson-Szpilman-Srivastava metoda funkcji bariera miała liczbę wniosków do geometrii i analizy funkcjonalnej, powstała w informatyce, i jest to bardzo oryginalna forma potencjalnej funkcji argumentu, przypomina metody pesymistycznych estymatorów. Co więcej, sprzeczne jest z konwencjonalną mądrością, że analiza charakterystycznego wielomianu macierzy losowych jest trudna do rozwiązania, a zamiast tego lepiej jest spojrzeć na momenty macierzy.

Metoda funkcji barierowej została po raz pierwszy opracowana w celu udowodnienia istnienia (i skonstruowania w deterministycznym czasie wielomianowym) sparsyfikatorów grafów, które zachowują ich właściwości spektralne. Takie sparyfikatory były motywowane przez aplikacje algorytmiczne: zasadniczo każdy algorytm, który musi w przybliżeniu obliczać cięcia, można przyspieszyć, podając jako dane wejściowe sparfikowaną wersję oryginalnego wejścia.

$\ell_1^n$

Szybko do 2013 r., A metoda funkcji barierowej na sterydach i wzmocniona maszynerią przeplatających się wielomianów została wykorzystana przez Marcusa, Srivastava i Spielmana do rozwiązania jednego z najbardziej znanych problemów w analizie funkcjonalnej, problemu Kadisona-Singera . Problem ten wynika z podstawowych pytań w fizyce matematycznej, ale idzie znacznie dalej - wiadomo, że jest równoważny dziesiątkom problemów w całej matematyce. Nie wspominając o tym, że wielu analityków (w tym Kadison i Singer) nawet nie uważało, że problem został rozwiązany pozytywnie (cytowane badanie Cassazy i wsp. Spekuluje na temat możliwych kontrprzykładów).

Jednym z przykładów, który przychodzi mi na myśl, jest twierdzenie Higmana o osadzeniu i jego grupowe konsekwencje teoretyczne.

Twierdzenie Higmana o osadzeniu: Grupa G jest generowana w sposób skończony z rekurencyjną prezentacją iff G to podgrupa grupy przedstawionej w sposób skończony.

(Zauważ, że lewa część ekwiwalencji ma element obliczeniowy, podczas gdy prawa jest czysto teoretyczna dla grupy).

Znaczenie losowości , co stanowi „losową sekwencję” i powiązane pytania, były ważne w matematyce, teorii prawdopodobieństwa i statystyce przez wieki. Informatyka teoretyczna (i teoria złożoności) oferuje bardzo solidne, głębokie i przekonujące informacje dla zrozumienia losowości.

Podczas gdy metoda probabilistyczna rozpoczęła się w matematyce, derandomizacja, która jest ważną koncepcją matematyczną, jest rozwijana głównie w CS.

Jest to związane z odpowiedzią Moritza .

Teoria automatów i algebraiczność

Teoria automatów dała kilka interesujących wyników w celu scharakteryzowania algebraiczności. Wspominam o dwóch z odniesieniami. W żadnym wypadku nie jest to wyczerpujące.

$\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. Liczby transcendentalne

Automatyczne sekwencje są również używane do charakteryzowania liczb transcendentalnych. Na przykład,

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

Oczywiście pierwszy przedmiot to bardzo klasyczny wynik!

Bibliografia.

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

[2] Kiran S. Kedlaya. Automaty skończone i rozszerzenia algebraiczne pól funkcyjnych . W Journal de théorie des nombres de Bordeaux 18 , s. 379–420, 2006. arXiv: math / 0410375 .

[3] Boris Adamcweski, Yann Bugeaud. O złożoności liczb algebraicznych I. Rozwinięcia w liczbach całkowitych . W Annals of Mathematics 165 (2), s. 547–565, 2007.

$L$$\tau$

$L$

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

IMHO TCS jest gałęzią matematyki i powiedziałbym, że jest nieco szersza. Żyjemy w erze algorytmicznej, prawie wszyscy, we wszystkich ludzkich działaniach, wynajdują / odkrywają algorytmy, głównie heurystykę. Ale niektóre z tych algorytmów są 1. dobre; 2. zawierać (zakopane) odpowiedzi na głębokie pytania matematyczne; 3. Poczekaj na profesjonalną analizę matematyczną / poprawę / uwagę. Moje osobiste doświadczenie: oszałamiająca moc jednego heurystycznego fizyki / uczenia maszynowego, a mianowicie przybliżenie Bethe, jako technika dowodowa. Główny problem polega na tym, że tego rodzaju potencjalne spotkania zdarzają się głównie w branży, gdzie nikt nie dba o te spostrzeżenia / objawienia niezwiązane z produktem.