Przykłady „niepowiązanej” matematyki grającej podstawową rolę w TCS?

Proszę wymienić przykłady, w których twierdzenie matematyki, które normalnie nie było uważane za stosowane w informatyce, zostało po raz pierwszy wykorzystane do udowodnienia wyniku w informatyce. Najlepszymi przykładami są te, w których połączenie nie było oczywiste, ale kiedy zostało odkryte, jest to wyraźnie „właściwy sposób”, aby to zrobić.

To jest odwrotny kierunek pytania Zastosowania TCS do matematyki klasycznej?

Na przykład patrz „Twierdzenie Greena i izolacja w grafach planarnych” , gdzie twierdzenie o izolacji (znane już przy użyciu dowodu technicznego) zostało ponownie udowodnione przy użyciu twierdzenia Greena z rachunku wielowymiarowego.

Jakie są inne przykłady?

Maurice Herlihy, Michael Saks, Nir Shavit i Fotios Zaharoglou otrzymali nagrodę Godela w 2004 roku za wykorzystanie topologii algebraicznej w badaniu niektórych problemów w przetwarzaniu rozproszonym.

Mam przykład z pracy, którą współtworzyłem kilka lat temu z Nogą Alon i Mulim Safrą:

Noga zastosował twierdzenia algebraiczne o topologii punktowej, aby udowodnić „Twierdzenie o podziale naszyjników”: jeśli masz naszyjnik z koralikami typu t i chcesz podzielić jego części na b, aby każdy otrzymał tę samą liczbę koralików z każdego typu ( zakładając, że b dzieli t), zawsze możesz to zrobić, przecinając naszyjnik w co najwyżej (b-1) t miejscach.

Wykorzystaliśmy to twierdzenie do skonstruowania obiektu kombinatorycznego, którego użyliśmy do udowodnienia twardości aproksymacji Set-Cover.

Więcej informacji znajduje się tutaj: http://people.csail.mit.edu/dmoshkov/papers/k-restrictions/k-rest.html

Z perspektywy czasu może to być oczywiste, ale zawsze lubiłem stosowanie przez Steele, Yao i Bena-Or twierdzenia Oleinika-Pietrowskiego / Milnora / Thoma (ograniczającego liczby Bettiego prawdziwych zbiorów półalgebraicznych), aby udowodnić, że są niższe granice w algebraicznym drzewie decyzyjnym i algebraicznym drzewie obliczeniowym modeli obliczeniowych.

Jednym z moich ulubionych rezultatów jest użycie argumentów topologicznych w dowodzie Lovaszowskiej hipotezy Knesera oraz zastosowanie metod topologicznych ( i teoretycznych grupowych ) w ataku Kahna-Saksa-Sturtevanta na silną hipotezę Aandery-Rosenberga-Karpa o wymijaniu .

Teoria reprezentacji grup skończonych jest stosowana w podejściu Cohna-Kleinberga-Szegedy-Umansa do mnożenia macierzy . Pokazują, że jeśli istnieją rodziny produktów wieńcowych abelowych z grupami symetrycznymi spełniającymi określone warunki, to istnieją algorytmy mnożenia macierzy o kwadratowej złożoności.

Teoria reprezentacji (grup algebraicznych) pojawia się także w podejściu teorii złożoności geometrycznej Mulmuleya i Sohoni'ego do dolnych granic. Nie jest jeszcze jasne, czy liczy się to jako aplikacja, ponieważ przy takim podejściu nie udowodniono jeszcze nowych wyników złożoności, ale między dwoma obszarami, które na pierwszy rzut oka wydają się zupełnie niezwiązane, stworzono przynajmniej ciekawe połączenie.

Istnieje wiele takich przykładów. Kiedy po raz pierwszy nauczyłem się teorii złożoności, zaskoczyło mnie, że podstawowe twierdzenia o pierwiastkach wielomianów (takie jak Schwartz-Zippel-DeMillo-Lipton Lemma) miały coś wspólnego z pytaniem, czy dowody interaktywne mogą symulować przestrzeń wielomianową ( ). Oczywiście te właściwości wielomianów były już wykorzystywane we wcześniejszych pracach, a obecnie stosowanie obliczeń „wielomianowych” stało się dość standardowe w teorii złożoności.$IP = PSPACE$

Teoria aproksymacji (która zajmuje się przybliżaniem możliwie skomplikowanych lub nienaturalnych funkcji o wartościach rzeczywistych za pomocą prostych funkcji, takich jak wielomiany niskiego stopnia) ma wiele zastosowań w złożoności obwodu, złożoności kwantowej kwerendy, pseudolosowości itp.

Myślę, że jedno z najfajniejszych zastosowań narzędzi z tego obszaru pochodzi z tego artykułu Beigela, Reingolda i Spielmana, w którym wykazano, że klasa złożoności PP jest zamknięta pod przecięciem, wykorzystując fakt, że funkcję znaku można aproksymować niskim -stopniowa funkcja wymierna.

Nisan, Szegedy i Paturi wykazali niższe granice aproksymacji funkcji symetrycznych przez wielomiany niskiego stopnia. Ta metoda jest często stosowana do udowodnienia dolnych granic złożoności kwantowej kwerendy. Zobacz na przykład notatki z wykładu Scotta Aaronsona .

Kolejny piękny pomysł: pomysł Yao, aby zastosować zasady minimax i dowód, że gry mieszane mają równowagę (zasadniczo dualność programowania liniowego), aby pokazać dolne granice algorytmów losowych (zamiast budowania rozkładu danych wejściowych do algorytmu deterministycznego).

Twierdzenia o punktach stałych są wszędzie ...

Ale dość zaskakujący przykład wyskakiwania geometrii znikąd jest skutecznym wynikiem porównania. Tutaj, biorąc pod uwagę częściowy porządek zdefiniowany w zbiorze elementów, rozważ zestaw permutacji obiektów, które są kompatybilne z danym porządkiem częściowym. Pytanie polega na wybraniu najskuteczniejszego porównania do wykonania; to jest porównanie, które zmniejszyłoby liczbę permutacji zgodnych z nowym porządkiem częściowym (oczywiście są dwa możliwe porządki częściowe, w zależności od wyniku tego pojedynczego porównania). Wiadomo, że zawsze istnieje porównanie, które zmniejsza liczbę permutacji o stały współczynnik (dlatego można sortować wO ( log n ! $n$$O(\log n!)$porównania, duh). Dowodem na to jest geometria wielowymiarowych polytopów. W szczególności dowód wykorzystuje nierówność Brunna-Minkowskiego. Dobra prezentacja tego znajduje się w książce Matousek na temat wykładów z geometrii dyskretnej (rozdział 12.3). Oryginalny dowód pochodzi od Kahna i Linial, stąd .

Istnieje wiele zastosowań teorii informacji w informatyce teoretycznej: np. W dowodzeniu dolnych granic dla kodów dekodowanych lokalnie (patrz Katz i Trevisan), w dowodzie Raza na twierdzenie o równoległym powtarzaniu, w złożoności komunikacyjnej (patrz na przykład wątek prac nad kompresją komunikacji, np. stosunkowo niedawna praca Baraka, Bravermana, Chena i Rao oraz odnośniki tam zawarte) i wiele innych prac.

Alon i Naor wykorzystali nierówność Grothendiecka do udowodnienia algorytmu aproksymacji problemu maksymalnego cięcia . Myślę, że są kolejne prace na ten temat, ale nie jestem ekspertem.

Co ciekawe, to samo twierdzenie zastosowali Cleve, Hoyer, Toner i Watrous do analizy kwantowych gier XOR, a Linial i Shraibman zastosowali je do złożoności komunikacji kwantowej. O ile mi wiadomo, związek między nierównością Grothendiecka a fundamentem fizyki kwantowej został odkryty przez Tsirelsona w 85 roku, ale dwa wyniki, o których wspomniałem, dotyczą w szczególności informatyki.

Dobrym przykładem jest twierdzenie Barringtona:

Jeżeli funkcja boolowska jest obliczalna przez obwód o głębokości , to jest obliczalne przez program rozgałęziający o szerokości 5 i długości .d f 4 $f$$d$$f$$4^d$

Dowód wykorzystuje grupę (ponieważ ma dwa elementy, które są sprzężone ze sobą i z komutatorem), ale można ją uogólnić do pracy z dowolną nierozwiązywalną grupą.$S_5$

Bezwstydna wtyczka: zastosowanie hipotezy izotropowej (i ogólnie geometrii wypukłej) w projektowaniu w przybliżeniu optymalnych, różnicowo prywatnych mechanizmów dla zapytań liniowych w mojej pracy z Moritzem Hardtem .

Aby częściowo odpowiedzieć na powyższe pytanie Suresha, uważam, że pierwotne pytanie jest nieco trudne, ponieważ „zwykle nie uważa się go za zastosowanie w informatyce”. Niektóre z tych technik, które mogą wydawać się pierwotnie „niepowiązane”, stają się z czasem „normalne”. Zatem najbardziej udane z tych technik (np. Analiza Fouriera w Kahn-Kalai-Linial, osadzenie metryczne w Linial-London-Rabinovich) nie są już poprawnymi odpowiedziami.

Addytywna kombinatoryka / teoria liczb była często stosowana w literaturze ekstrakcyjnej. Myślę, że pierwsze przypadki wynikają z zauważenia, że ​​wykresy Paleya mogłyby być wykorzystane jako dobre ekstraktory, a niektóre otwarte pytania w teorii liczb addytywnych sugerowałyby lepsze. Najwcześniejszym odniesieniem, jakie znam, jest Zuckerman 1990 (patrz jego praca magisterska ), ale w ciągu ostatnich kilku lat był to obszar aktywny z interesującymi tam iz powrotem między TCS i kombinatoryką addytywną. (Jednym z najważniejszych wydarzeń jest dowód Dvir na skończoną hipotezę Kakeya, ale jest to oczywiście wkład TCS do matematyki, a nie na odwrót.) A-priori nie jest jasne, dlaczego tego rodzaju pytania matematyczne, sumy i produkty zestawów, byłoby ważne dla CS.

Sleator, Tarjan i Thurston udowodnili istnienie nieskończonej rodziny par binarnych drzew poszukiwań o nwierzchołkach i odległości obrotu 2n-6za pomocą geometrii hiperbolicznej.

Kombinatoryka addytywna używana do konstruowania jawnej macierzy RIP z wierszami :$o(k^2)$

Jean Bourgain, Stephen J. Dilworth, Kevin Ford, Sergei Konyagin, Denka Kutzarova: Przełamanie bariery dla wyraźnych macierzy RIP. STOC 2011: 637–644.$k^2$

Algebra liniowa używana do sparsify wykresów:

Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava: Dwa razy-ramanujan sparyfikatory. STOC 2009: 255–262.

To może, ale nie musi się liczyć, ale ostatnio teorie zbiorów Zermelo-Fraenkla z atomami (ZFA) i Fraenkela-Mostowskiego (FM) zostały zastosowane do badania abstrakcyjnej składni z wiązaniem nazw. ZFA została wprowadzona na początku XX wieku jako narzędzie do udowodnienia niezależności CH, a następnie zapomniana, ale odkryta pod koniec lat 90. XX wieku przez dwóch informatyków - Gabbaya i Pittsa - badających coś całkowicie niezwiązanego.

Zobacz na przykład ten artykuł ankietowy.

Zastosowanie entropii grafu przez Kahna i Kima do sortowania w ramach częściowych informacji (http://portal.acm.org/citation.cfm?id=129731). Podali pierwszy algorytm wielomianowy, który wykonuje teoretycznie optymalną (do stałych) liczbę porównań. Artykuł jest małą wyprawą z matematyki, wykorzystującą klasyczne argumenty kombinatoryczne, wraz z wypukłą geometrią, entropią wykresu i programowaniem wypukłym. Istnieje nowszy, prostszy algorytm, ale nadal wiemy, jak go analizować bez entropii wykresu.

Teorię liczb wykorzystano do opracowania RSA i innych schematów kryptograficznych z kluczem publicznym.

Odkrycie pomnożenia Karatsuba było zaskakujące.