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

74

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?

Derrick Stolee
źródło
Wiki społeczności.
Dave Clarke
Społeczność wiki jest już dostępna.
Derrick Stolee,
Zaskakujące, ile przykładów dotyczy topologii i geometrii. Czy jesteśmy bardziej zaskoczeni tymi dwoma tematami?
Suresh Venkat
7
Czy po podaniu wystarczającej liczby przykładów X obszar nie jest już „niezwiązany”?
András Salamon,

Odpowiedzi:

38

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.

Warren Schudy
źródło
1
To świetny przykład!
Ryan Williams,
25

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

Dana Moshkovitz
źródło
25

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.

Jeffε
źródło
1
„Z perspektywy czasu, to oczywiste” wyniki są najlepszym rodzajem aplikacji. Z perspektywy czasu jest 20/20.
Derrick Stolee
25

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 .

Suresh Venkat
źródło
+1. Wykorzystanie argumentów topologicznych do udowodnienia twierdzeń kombinatorycznych jest naprawdę epickie. Zainteresowani czytelnicy mogą znaleźć więcej informacji tutaj: en.wikipedia.org/wiki/Topological_combinatorics
Robin Kothari
1
@Robin: A co z argumentami geometrycznymi? Główne twierdzenie klasycznego artykułu Bayera-Diaconisa o tasowaniu jaskółczego ogona odkryto, myśląc o tasowaniu jako o transformacji zachowującej objętość (mapa piekarza: podwój i złóż (mod 1) wzdłuż każdej osi) 52-sześcianu. Niestety usunęli większość śladów geometrycznej intuicji z ostatecznej pracy, zastępując ją dyskretną kombinatoryką.
Per Vognsen,
@Per Vognsen: Nie znam tej pracy, więc dziękuję za wskaźnik. Rzucę na to okiem.
Robin Kothari,
2
Możesz dodać „ metody topologiczne i teoretyczne dla grupy ” dla Kahna-Saksa-Sturtevanta. W końcu oni wykorzystują działania grupowe na prostych kompleksach.
Joshua Grochow
2
Zastanawiałem się, czy warto „obudzić” ten wątek po roku, aby wskazać odniesienie ... ale to jest świetny wątek, więc dlaczego nie. Wynik Lovasha i inne wyniki, a także wprowadzenie do „topologii algebraicznej dla kombinatoryków” można znaleźć w monografii Matouseka
Sasho Nikolov
22

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.

Joshua Grochow
źródło
21

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

Ryan Williams
źródło
7
Podoba mi się też wielomianowa sztuczka polegająca na znajdowaniu idealnych dopasowań w grafach dwustronnych poprzez losowe próbkowanie wyznacznika (dzięki, Lovász).
Derrick Stolee,
21

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 .

Srikanth
źródło
20

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

Suresh Venkat
źródło
7
Również dowód Noama Nisana na twardy rdzeń Russella Impagliazza (w oryginalnym artykule Russella)
Dana Moshkovitz
17

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 ! )nO(logn!)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 .

Sariel Har-Peled
źródło
15

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.

Dana Moshkovitz
źródło
Ale czy te zastosowania są naprawdę „niepowiązane”? Przynajmniej z naiwnego punktu widzenia wydaje mi się, że teoria informacji jest jednym z pierwszych obszarów, które przychodzą mi na myśl, gdy po raz pierwszy słyszy się definicję, powiedzmy, kodów dekodowanych lokalnie.
arnab
Zgadzam się, że teoria informacji jest związana na przykład z kodami, a kody są związane z TCS. Równoległe powtarzanie jest być może silniejszym przykładem: dlaczego miałbyś pomyśleć o użyciu go do wzmocnienia głośności dla PCP?
Dana Moshkovitz
Tak, całkowicie się zgadzam, że równoległe powtarzanie jest zaskakującym przykładem.
arnab
14

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.

Marc
źródło
Uhm, to nie jest dokładne. Alon i Naor zbliżyli się do normy cięcia matrycy - jest to związane z maksymalnym cięciem, ale nie takie samo.
Sasho Nikolov
13

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 dfdf4d

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ą.S5

Diego de Estrada
źródło
12

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.

Kunal
źródło
Być może przeredaguję pytanie, aby rozwiązać ten problem.
Derrick Stolee
12

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.

Boaz Barak
źródło
6
innym dobrym przykładem w tym stylu jest niedawne użycie hipotezy Halesa-Jewitta w celu udowodnienia nieliniowej dolnej granicy siatki epsilon dla przestrzeni zasięgu wymiaru VC 2.
Suresh Venkat
11

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.

zotachidil
źródło
7

Kombinatoryka addytywna używana do konstruowania jawnej macierzy RIP z wierszami :o(k2)

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

Algebra liniowa używana do sparsify wykresów:

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

Jelani Nelson
źródło
6

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.

Dominic Mulligan
źródło
4

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.

Sasho Nikolov
źródło
3

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

Antonio Valerio Miceli-Barone
źródło
0

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

użytkownik3493
źródło
2
Gauss się nie zgodzi.
Jeffε