Zastosowania TCS w matematyce klasycznej?

60

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.

Joshua Grochow
źródło
1
Odpowiedź na to pytanie jest nieco trudna. Czy kombinatoryka wykracza poza klasyczną matematykę?
arnab
2
Kombinatoryka to zdecydowanie klasyczna matematyka, ale myślę, że ten sam komentarz dotyczy kombinatoryki, podobnie jak logiki. Tak więc: domysł Kakeya o skończonym polu jest dobrym przykładem, podczas gdy nowe kombinatoryczne projekty motywowane przez PRG są bardziej na płocie.
Joshua Grochow
Możesz znaleźć dobre przykłady, szukając wyników opublikowanych, powiedzmy, w Annals of Math przez społeczność TCS.
MCH

Odpowiedzi:

32

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

Gil Kalai
źródło
22

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

Dai Le
źródło
3
Przyczyną tego był problem dotyczący ekstraktorów / fuzji (patrz późniejszy artykuł Zeev i Avi Wigderson). Dalsze ulepszenia (Madhu Sudan, Shubhangi Saraf, Swastik Kopparty i Zeev Dvir) wykorzystały więcej pomysłów z teoretycznej informatyki, szczególnie z dekodowania kodów list (metoda wielokrotności).
Dana Moshkovitz
1
Dwie uwagi: Metoda algebraiczna stosowana przez Dvir jest jedną z metod stosowanych do rozwiązania klasycznego problemu dotyczącego odległości dla zbiorów płaskich. terrytao.wordpress.com/2010/11/20/… i gilkalai.wordpress.com/2010/11/20/… .
Gil Kalai
2
Po drugie, metody padania i wyniki z geometrii obliczeniowej i dyskretnej miały wcześniejsze zastosowania do (prawdziwego) problemu Kakeya.
Gil Kalai
20

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 nnFFnFn

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

Dana Moshkovitz
źródło
19

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 .

Manu
źródło
7
Ponadto można śmiało powiedzieć, że na elementy dowodu twierdzenia Szemerediego poprzez lemat o regularności hipergrafów (autorstwa Gowersa, Tao, Rodla, Schachta i innych) wpływ miała praca Alona, ​​Fischera, Shapiry i innych w opracowywaniu silniejszych wersji lemat regularności wykresu dla udowodnienia testowalności właściwości wykresu.
arnab
18

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

Aaron Sterling
źródło
2
Bez względu na to, czy liczysz obliczalność jako część TCS, uwielbiam ten przykład, o którym po prostu zapomniałem wspomnieć. Jest jeszcze fajniejszy, ponieważ można to zrobić przy użyciu złożoności Kołmogorowa :).
Joshua Grochow
17

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

Moritz
źródło
15

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

ilyaraz
źródło
13

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

Boaz Barak
źródło
10

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.

Gil Kalai
źródło
1
Nie wiedziałem, że inne dziedziny matematyki znacznie wykorzystały ideę redukcji. Byłbym bardzo wdzięczny za wszelkie odniesienia i wskazówki, które możesz podać do takich prac! Poza tym miałem wrażenie, że dowody probabilistyczne pochodzą z czystej kombinatoryki, a nie TCS?
Joshua Grochow
3
Wyjaśniłem, co rozumiem przez „dowód probabilistyczny” w edytowanej wersji mojej odpowiedzi. Odnośnie redukcji: złożoność obliczeniowa jest dziedziną matematyki zakorzenioną w informatyce. Jedną z cech charakterystycznych tego obszaru jest stosowanie redukcji, które odgrywają ważną rolę na poziomie koncepcyjnym i technicznym. Jest znacznie bardziej rozwinięty niż podobne techniki w innych obszarach matematyki. Tak więc sztukę redukcji w TCS można uznać za główne zastosowanie TCS w matematyce. Myślę, że redukcje typu CS wpłynęły na matematyków także w innych obszarach, a jeszcze więcej nie nastąpi.
Gil Kalai
Joshua, pozwól, że podam analogię. Załóżmy, że ktoś określa „rachunek różniczkowy” jako jedno z największych zastosowań fizyki w matematyce klasycznej. Można również powiedzieć, że rachunek różniczkowy jest ważny przede wszystkim do ataku na problemy fizyki, które wcześniej nie były „matematyką klasyczną”. Nadal uważam, że rachunek fizykalny jest głównym wkładem fizyki w matematykę. Podobnie, redukcje typu stosowanego w teorii złożoności są głównym wkładem TCS w matematykę. Opisuje główny aparat matematyczny i idee matematyczne, które mają niezależną wartość (choć nie tak ważne jak rachunek różniczkowy)
Gil Kalai
G
1
@JoshuaGrochow nie będzie trudno znaleźć nietrywialne przykłady „ogólnych przypadków specjalnych zniżek”. Na przykład ankieta Cassaza, którą podałem w odpowiedzi, zawiera mnóstwo nietrywialnych redukcji między problemami równoważnymi problemowi Kadisona-Singera, niektóre z nich są bardzo ograniczone na pierwszy rzut oka. Rozumiem, że geometria arytmetyczna jest również pełna takich rzeczy, możesz wiedzieć więcej. Nie jestem pewien, do jakiego stopnia TCS może domagać się uznania za wprowadzenie tego podejścia do trudnych problemów.
Sasho Nikolov
9

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.

Peter Shor
źródło
9

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.

1n

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

Sasho Nikolov
źródło
5

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

Mike
źródło
1
GHGWord(G)NPG
5

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 .

Gil Kalai
źródło
5

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.

Fq(t)

Fq(t)qq=pspsFq[[t]]Fq

Fq(t)Fq(t)

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

Fq(t)

iIxiti,
IQFq(t)

iIaitiFq(t){ai}iIp

2. Liczby transcendentalne

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

b2xRx={xi}i=0b

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

Bruno
źródło
twierdzenie (Adamczewski i Bugeaud [3]) może być błędne lub źle zrozumiane
XL _At_Here_There
4

Lτ

L

τpτ(1+τ)cc

Bruno
źródło
1

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.

leonid gurvits
źródło