Teoria informacji użyta do udowodnienia trafnych twierdzeń kombinatorycznych?

Jakie są twoje ulubione przykłady, w których teoria informacji jest wykorzystywana do udowodnienia zgrabnego kombinatorycznego stwierdzenia w prosty sposób?

Niektóre przykłady, które mogę wymyślić, są związane z dolnymi granicami dla dekodowanych lokalnie kodów, np. W tym artykule: załóżmy, że dla wiązki ciągów binarnych długości ma to, że dla każdego , dla różny pary { },Zatem m jest co najmniej wykładnicze w n, gdzie wykładnik zależy liniowo od średniego stosunku . n i k i j 1 , j 2 e i = x j 1 ⊕ x j 2 . k i /$x_1,...,x_m$$n$$i$$k_i$$j_1,j_2$

Innym (pokrewnym) przykładem są pewne nierówności izoperymetryczne na kostce boolowskiej (prosimy o rozwinięcie tego w odpowiedziach).

Czy masz więcej fajnych przykładów? Najlepiej krótki i łatwy do wyjaśnienia.

Dowód Mosera o konstruktywnej lemacie Lovasz . Zasadniczo pokazuje, że w warunkach lokalnego lematu, drugi najprostszy algorytm dla SAT, który można wymyślić, działa. (Pierwszym najprostszym może być po prostu wypróbowanie losowego przydziału, dopóki jedno nie zadziała. Dowód, że działa to w czasie wielomianowym, jest prawdopodobnie najbardziej eleganckim zastosowaniem teorii informacji (lub złożoności Kołmogorowa, jakkolwiek chcesz to nazwać w tym przypadku), jaką kiedykolwiek widziałem.

Moim ulubionym przykładem tego typu jest oparty na entropii dowód Lemmy Shearera. (Dowiedziałem się o tym dowodzie i kilku innych bardzo ładnych z Entropii i liczenia Jaikumara Radhakrishnana .)

Twierdzenie: Załóżmy, że punktów w R 3 , które n x Najpierw odrębne występy na y oo -plane, n y odrębne występy na x oo -plane i n ż odrębne występy na x y -plane. Następnie n 2 ≤ n x n y n z .$n$$\mathbb{R}^3$$n_x$$yz$$n_y$$xz$$n_z$$xy$$n^2 \leq n_x n_y n_z$

Dowód: Niech będzie punktem losowo wybranym losowo spośród n punktów. Niech p x , p y , p z oznaczają jego rzuty odpowiednio na płaszczyzny y z , x z i x y . $p = (x,y,z)$$n$$p_x$$p_y$$p_z$$yz$$xz$$xy$

Z jednej strony , H [ p x ] ≤ log n x , H [ p y ] ≤ log n y i H [ p z ] ≤ log n z , przez podstawowe właściwości entropii.$H[p] = \log n$$H[p_x] \leq \log n_x$$H[p_y] \leq \log n_y$$H[p_z] \leq \log n_z$

Z drugiej strony mamy a także H [ p x ] = H [ y ] + H [ z | y ] H [ p y ] = H [ x ] + H [

Mamy zatem lub n 2 ≤ n x n y n z .$2 \log n \leq \log n_x + \log n_y + \log n_z$$n^2 \leq n_x n_y n_z$

Dowód Radhakrishnana dla twierdzenia Bregmana, że ​​liczba idealnych dopasowań na wykresie dwudzielnym ( L ∪ R , E ) wynosi co najwyżej ∏ v ∈ L ( d ( v ) ! ) 1 / d ( v ) . Dowód wykorzystuje dwa bardzo sprytne pomysły. Oto szkic dowodu:$p$$(L\cup R, E)$$\prod_{v \in L} (d(v)!)^{1/d(v)}$

• Wybierz idealnie pasujące równomiernie. Entropia tej zmiennej to H ( M ) = log p .$M$$H(M) = \log p$
• Na , niech x V jest wierzchołek w R , który jest dopasowany do V w M .$v \in L$$X_v$$R$$v$$M$
• Zmienna ma takie same informacje jak M , więc H ( M ) = H ( X ) .$X = (X_v : v \in L)$$M$$H(M) = H(X)$
• Sprytna idea 1: Poprzez losowe (i jednolite) wybranie rzędu na L , Radhakrishnan zapewnia „losową regułę łańcucha” stwierdzającą H ( X ) = ∑ v ∈ L H ( X v | X u : u < v , ≤ ) .$\leq$$L$$H(X) = \sum_{v\in L} H(X_v | { X_u : u < v }, \leq)$
• Na podstawie informacji w warunkach ( ) możemy określić N v = | N ( v ) ∖ X u : u < v | (z grubsza: liczba opcji dopasowania v ).${X_u : u < v}, \leq$$N_v = |N(v) \setminus { X_u : u < v }|$$v$
• Ponieważ jest określana na podstawie tych informacji, uwarunkowana entropia nie zmienia w zakresie równości H ( X v | X u : u < v , ≤ ) = H ( X v | X u : u < v , ≤ , N v ) .$N_v$$H(X_v | { X_u : u < v }, \leq) = H(X_v | { X_u : u < v }, \leq, N_v)$
• Sprytna idea 2: „Zapominając” o informacjach , możemy jedynie zwiększyć entropię: H ( X v | X u : u < v , ≤ , N v ) ≤ H ( X v | N v ) .${X_u : u < v}, \leq$$H(X_v | { X_u : u < v }, \leq, N_v) \leq H(X_v | N_v)$
• Szalony fakt: Zmienna jest równomiernie rozłożona na zbiorze 1 , … , d ( v ) .$N_v$${1,\dots, d(v)}$
• Teraz, aby obliczyć entropię , sumujemy wszystkie wartości N v : H ( X v | N v ) = ∑ d ( v ) i = 1$H(X_v | N_v)$$N_v$$H(X_v | N_v) = \sum_{i=1}^{d(v)} \frac{1}{d(v)}H(X_v|N_v=i) \leq \frac{1}{d(v)}\sum_{i=1}^{d(v)}\log i = \log((d(v)!)^{1/d(v)}).$
• Wynik wynika z połączenia wszystkich nierówności i wzięcia wykładników.

Uogólnienie tej nierówności jest Kahn-Lovász Twierdzenie Numer doskonałych skojarzeń w każdym wykresie wynosi co najwyżej gatunku V ∈ V ( G ), ( d ( v ) ! ) 1 / 2 d ( v ) . Dowód entropii tego wyniku został udowodniony przez Cutlera i Radcliffe'a .$G$$\prod_{v \in V(G)} (d(v)!)^{1/2d(v)}$

Bardzo ładne przykłady zawarte są w dwóch artykułach Pippengera Anonimowo-teoretyczna metoda w teorii kombinatorycznej. J. Comb. Teoria, Ser. A 23 (1): 99-104 (1977) oraz Entropia i wyliczenie funkcji boolowskich. Transakcje IEEE dotyczące teorii informacji 45 (6): 2096–2100 (1999). W rzeczywistości kilka prac Pippengera zawiera urocze dowody kombinatorycznych faktów za pomocą entropii / wzajemnej informacji. Dwie książki: Jukna, Extremal Combinatorics With Applications in Computer Science i Aigner, Combinatorial Search mają kilka dobrych przykładów. Lubię też dwa artykuły Madiman i in. Teoretyczne nierówności w addytywnym kombinatoryka i Terence Tao, szacunki sum Entropy (można je znaleźć w Google Scholar). Mam nadzieję, że to pomoże.

Innym świetnym przykładem jest alternatywny dowód Terry Tao na lemat o regularności wykresu Szemerédiego . Używa perspektywy teoretycznej, aby udowodnić silną wersję lematu regularności, co okazuje się niezwykle przydatne w jego dowodzie lematu regularności dla hipergraphów . Dowód Tao jest jak dotąd najbardziej zwięzłym dowodem lematu o regularności hipergrafów.

Pozwól, że spróbuję wyjaśnić na bardzo wysokim poziomie tę teoretyczną informację.

Załóżmy, że masz dwuczęściowy wykres z dwoma zestawami wierzchołków V 1 i V 2 oraz zestawem brzegowym E podzbiorem V 1 × V 2 . Gęstość krawędzi G wynosi ρ = | E | / | V 1 | | V 2 | . Mówimy, G jest ε -regular jeżeli dla wszystkich U 1 ⊆ V 1 i U 2 ⊆ V $G$$V_1$$V_2$$V_1 \times V_2$$G$$\rho = |E|/|V_1||V_2|$$G$$\epsilon$$U_1 \subseteq V_1$$U_2 \subseteq V_2$, gęstość krawędzi podsgrafu indukowana przez i U 2 wynosi ρ ± ϵ | U 1 | | U 2 | / | V 1 | | V 2 | .$U_1$$U_2$$\rho \pm \epsilon |U_1||U_2|/|V_1||V_2|$

Teraz rozważ wybranie wierzchołka z V 1 i wierzchołka x 2 z V 2 , niezależnie i równomiernie losowo. Jeśli ε jest mały i U 1 , U 2 są duże, możemy interpretować ε -regularity z G jak mówienie, że klimatyzacja x 1 aby być w U 1 i x 2 , aby być w U 2 nie wpływa znacznie prawdopodobieństwo, że ( x 1 , x $x_1$$V_1$$x_2$$V_2$$\epsilon$$U_1, U_2$$\epsilon$$G$$x_1$$U_1$$x_2$$U_2$ Tworzy krawędź z G . Innymi słowy, nawet po otrzymaniu informacji, że x 1 jest w U 1, a x 2 jest w U 2 , nie uzyskaliśmy wielu informacji na temat tego, czy ( x 1 , x 2 ) jest krawędzią, czy nie.$(x_1,x_2)$$G$$x_1$$U_1$$x_2$$U_2$$(x_1,x_2)$

Lemat Szemeredi (nieformalnie) gwarantuje, że dla każdego wykresu można znaleźć podział i podział V 2 na podzbiory o stałej gęstości, tak że dla większości takich par podzbiorów U 1 ⊂ V 1 , U 2 ⊂ V 2 , indukowany wykres podrzędny na U 1 × U 2 jest ϵ- nieregularny. Dokonując powyższej interpretacji, biorąc pod uwagę dowolne dwie zmienne o wysokiej entropii x 1 i x 2 , oraz dane dowolne zdarzenie E ( $V_1$$V_2$$U_1 \subset V_1, U_2 \subset V_2$$U_1 \times U_2$$\epsilon$$x_1$$x_2$ , możliwe jest znalezienie zmiennych o niskiej entropii U 1 ( x 1 ) i U 2 ( x 2 ) - „niska entropia”, ponieważ podzbiory U 1 i U 2 mają stałą gęstość - takie że E jest w przybliżeniu niezależne od x 1 | U 1 i x 2 | U $E(x_1,x_2)$$U_1(x_1)$$U_2(x_2)$$U_1$$U_2$$E$$x_1 | U_1$$x_2 | U_2$lub że wzajemna informacja między zmiennymi jest bardzo mała. Tao faktycznie formułuje znacznie silniejszą wersję lematu regularności, używając tego ustawienia. Na przykład, nie wymaga on, aby i x 2 były zmiennymi niezależnymi (chociaż, o ile wiem, nie było jeszcze zastosowania tego uogólnienia). $x_1$$x_2$

Zasadniczo jest to cały kurs poświęcony temu pytaniu:

https://catalyst.uw.edu/workspace/anuprao/15415/86751

Kurs wciąż trwa. Dlatego nie wszystkie notatki są dostępne w chwili pisania tego. Ponadto niektóre przykłady z kursu zostały już wspomniane.

$n$$\ell_2^d$$1 \pm \epsilon$$d$$O(\log n / \epsilon^2)$$\Omega(\log n / (\epsilon^2 \log(1 / \epsilon)))$$\sim \log(1 / \epsilon)$

$m$$u \in [m]$$x \in [m]$$x=u$$t$$t$

$O(m^{1/t})$$\log m$$u$$t$$i \in [t]$$(\log m)/t$$i$$u$

$X$$[m]$$H[X] = \log m$$X_1, \dots, X_t$$t$$H[X] = H[X_1] + H[X_2 | X_1] + \cdots + H[X_t | X_1, \dots, X_{t-1}] \leq t \log s$$s$$s \geq m^{1/t}$

$t > 1$

$P$$P$$O(\log |X|)$$X$$P$

Analiza średnich przypadków algorytmów wykorzystujących złożoność Kołmogorowa przez Jiang, Li, Vitanyi.

„Analiza złożoności algorytmów średniej wielkości przypadków jest bardzo praktycznym, ale bardzo trudnym problemem w informatyce. W ciągu ostatnich kilku lat wykazaliśmy, że złożoność Kołmogorowa jest ważnym narzędziem do analizy złożoności algorytmów w średnich przypadkach. Opracowaliśmy metodę nieściśliwości [7]. W tym artykule wykorzystujemy kilka prostych przykładów, aby dodatkowo zademonstrować moc i prostotę takiej metody. Udowadniamy ograniczenia średniej liczby stosów (kolejek) wymaganych do sortowania sekwencyjnego lub równoległego Queueusort lub Stacksort. ”

Zobacz także np. Złożoność Kołmogorowa i problem trójkąta typu Heilbronna .

Równoważność pobierania próbek i wyszukiwania przez Scotta Aaronsona. Tutaj pokazuje równoważność problemu próbkowania i poszukiwania w teorii złożoności w odniesieniu do ważności rozszerzonej tezy Church-Turinga. Standardowa teoria informacji, algorytmiczna teoria informacji i złożoność Kołmogorowa są wykorzystywane w fundamentalny sposób.

Podkreśla:
„ Podkreślmy, że nie używamy złożoności Kołmogorowa jedynie jako wygody technicznej lub jako skrótu do liczenia argumentów. Raczej złożoność Kołmogorowa wydaje się niezbędna nawet do zdefiniowania problemu wyszukiwania. ”

To proste, a także przybliżenie: ile kombinacji 10 ⁶ rzeczy z 10 ⁹ , pozwalając na duplikaty? Prawidłowa formuła to

N = (10 ⁶ + 10 ⁹ )! / (10 ⁶ ! 10 ⁹ !) ~ = 2 ^{11409189.141937481}

Ale wyobraź sobie, że dajesz instrukcje, aby przejść wzdłuż rzędu miliarda wiader, zrzucając milion kulek do wiader po drodze. Będzie ~ 10 ⁹ instrukcji „krok do następnego wiadra” i 10 ⁶ instrukcji „upuść marmur”. Łączna informacja to

log ₂ (N) ~ = -10 ⁶ log ₂ (10 ⁶ / (10 ⁶ + 10 ⁹ )) - 10 ⁹ log ₂ (10 ⁹ / (10 ⁶ + 10 ⁹ )) ~ = 11409200.432742426

co jest zabawnym, ale całkiem dobrym sposobem na przybliżenie liczby (dziennika). Podoba mi się, ponieważ działa, jeśli zapomnę, jak robić kombinatorykę. Jest to równoważne z powiedzeniem tego

(a + b)! / a! b! ~ = (a + b) ^{(a + b)} / a ^a b ^b

co jest jak użycie przybliżenia Stirlinga, anulowanie i pominięcie czegoś.

Bardzo ładna niedawna aplikacja do wyznaczania górnych granic permutacji wysokowymiarowych przez Linial i Lurię znajduje się tutaj: http://www.cs.huji.ac.il/~nati/PAPERS/hd_permutations.pdf