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?


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:



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


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.


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 .


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


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


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 .


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


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 .


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.


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.


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


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.


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.


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


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.


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.


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.



Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.