Czysto teoretyczne objaśnienie redukcji z Unique Label Cover do Max-Cut

Studiuję Unique Games Conjecture i słynną redukcję do Max-Cut Khota i in. Ze swojej pracy i innych stron internetowych większość autorów używa (jak dla mnie) niejawnej równoważności między redukcją MAX-CUT a budowaniem konkretnych testów dla długich kodów. Z powodu mojego braku jasności co do tej równoważności staram się podążać tym tokiem myślenia.

Wydaje się również jasne z tych ekspozycji, że redukcję można opisać wyłącznie w kategoriach grafów, ale że przypadkiem lub preferencją nikt nie wybiera takiego sposobu. Na przykład w tych notatkach z wykładów O'Donnella wskazuje, że test długiego kodu odpowiada naturalnej definicji krawędzi tworzonego wykresu, ale ponieważ nie jest to wyjaśnione, reguła wydaje się zależeć od wyboru cięcia aby zdefiniować testowaną funkcję boolowską, co spowodowało, że byłem raczej zdezorientowany.

Proszę więc, żeby ktoś wyjaśnił redukcję „tylko” graficznie teoretycznie. Myślę, że to pomoże mi zrozumieć równoważność między dwoma punktami widzenia.

Zobaczę, czy mogę to wyjaśnić na wysokim poziomie. Załóżmy, że instancja UG jest grafem dwustronnym$G = (V \cup W, E)$, bijections $\{\pi_e\}_{e \in E}$, gdzie $\pi_e\colon \Sigma \to \Sigma$, i $|\Sigma| = m$. Chcesz zbudować nowy wykres$H$ więc jeśli instancja UG to $1-\delta$ zadowalający więc $H$ ma duże cięcie, a jeśli wystąpienie UG nie jest nawet $\delta$-satysfakcjonujące zatem $H$ ma tylko bardzo małe kawałki.

Wykres $H$ zawiera, dla każdego wierzchołka w $W$, chmura $2^m$ punkty, każdy oznaczony przez niektórych $x \in \{-1, 1\}^\Sigma$. Chodzi o to, że powinieneś być w stanie zinterpretować kodowanie długiego kodu etykiet$W$ jako kawałek $H$. Przypomnij sobie, aby zakodować niektóre$\sigma \in \Sigma$ z długim kodem używasz funkcji boolowskiej $f\colon \{-1, 1\}^\Sigma \to \{-1, 1\}$; w szczególności jest to funkcja dyktatora$f(x) = x_\sigma$. Zróbmy cięcie$S\cup T$(tj. bi-partycja wierzchołków) z kodowania długiego kodu w następujący sposób. Gdyby$w \in W$ ma etykietę zakodowaną przez funkcję boolean $f$, przejdź do chmury wierzchołków w $H$ odpowiadającej $w$i włóż $S$ wszystkie wierzchołki w chmurze oznaczone przez niektórych $x$ dla którego $f(x) = 1$. Wszyscy inni idą do$T$. Możesz to zrobić wstecz, aby przypisać wszystkim funkcje boolowskie$w \in W$ na podstawie cięcia $H$.

Aby redukcja zadziałała, musisz być w stanie powiedzieć tylko patrząc na wartość cięcia$S\cup T$ czy funkcje boolowskie odpowiadające cięciu są zbliżone do długiego kodu kodującego pewne przypisanie etykiet do $W$ który spełnia wiele ograniczeń UG $G$. Pytanie brzmi, jakie informacje otrzymujemy z wartości cięcia$S \cup T$. Rozważ dowolne dwa wierzchołki$a$ z etykietą $x$ w chmurze odpowiadającej $w$ i $b$ z etykietą $y$ w chmurze odpowiadającej $w'$ (w redukcji patrzymy tylko $w$, $w'$w różnych chmurach). Powiedzieliśmy, że cięcie można wykorzystać do uzyskania funkcji boolowskich$f_w$ i $f_{w'}$. Teraz, jeśli jest krawędź$(a,b)$ w $H$, następnie $(a, b)$ jest cięty wtedy i tylko wtedy $f_w(x) \neq f_{w'}(y)$. Dlatego użycie tylko wartości cięcia, aby stwierdzić, czy wywoływane przez nią funkcje boolowskie są „dobre”, jest tym samym, co test, który przy danych funkcjach boolowskich$\{f_w\}_{w \in W}$, pyta tylko o ułamek określonej listy par $((w, x), (w', y))$ mamy $f_w(x) \neq f_{w'}(y)$.

Innymi słowy, ilekroć Ryan mówi w notatkach „testuj jeśli $f_w(x) \neq f_{w'}(y)$„to, co tak naprawdę ma na myśli, to„ w $H$, dodaj krawędź między wierzchołkiem w chmurze $w$ oznaczone przez $x$ i wierzchołek w chmurze $w'$ oznaczone przez $y$„Tj. Dla każdego $v\in V$, co dwaj jego sąsiedzi $w, w'$i każdy $x,y \in \{-1, 1\}^n$, uwzględnij krawędź między wierzchołkiem w chmurze $w$ oznaczone przez $x\circ \pi_{v,w}$ i wierzchołek w chmurze $w'$ oznaczone przez $y \circ \pi_{v,w'}$i przypisz wagę krawędzi $(({1-\rho})/{2})^d(({1+\rho})/{2})^{n-d}$ gdzie $d$ to odległość Hamminga między $x$ i $y$. W ten sposób wartość cięcia podzielona przez całkowitą masę krawędzi jest dokładnie równa prawdopodobieństwu sukcesu testu.