Une explication purement théorique de la réduction de la couverture d'étiquette unique à Max-Cut

J'étudie la Conjecture Unique Games et la fameuse réduction à Max-Cut de Khot et al. À partir de leur article et ailleurs sur Internet, la plupart des auteurs utilisent (ce qui pour moi est) une équivalence implicite entre la réduction MAX-CUT et la construction de tests particuliers pour les codes longs. En raison de mon propre manque de clarté sur cette équivalence, j'ai du mal à suivre ce train de pensée.

Il apparaît également clairement à partir de ces expositions que l'on pourrait décrire la réduction uniquement en termes de graphiques, mais que par coïncidence ou préférence personne ne choisit de le faire de cette façon. Par exemple, dans ces notes de cours d'O'Donnell, il laisse entendre que le test de code long correspond à une définition naturelle des bords du graphique en cours de construction, mais comme il n'est pas précisé, cette règle semble dépendre du choix d'une coupe pour définir la fonction booléenne en cours de test, et cela m'a laissé assez confus.

Je demande donc à quelqu'un d'expliquer la réduction "juste" graphiquement. Je pense que cela m'aidera à comprendre l'équivalence entre les deux points de vue.

Permettez-moi de voir si je peux clarifier cela, à un niveau élevé. Supposons que l'instance UG soit un graphe biparti , bijections { π e } e ∈ E , où π e : Σ → Σ , et | Σ | = m . Vous voulez construire un nouveau graphe H de sorte que si l'instance UG est 1 - δ satisfaisable, alors H a une coupe importante, et si l'instance UG n'est même pas δ -satisfiable, alors$G = (V \cup W, E)$$\{\pi_e\}_{e \in E}$$\pi_e\colon \Sigma \to \Sigma$$|\Sigma| = m$$H$$1-\delta$$H$$\delta$ n'a que de très petites coupures.$H$

Le graphe contient, pour chaque sommet de W , un nuage de 2 m points, chacun étiqueté par quelques x ∈ { - 1 , 1 } Σ . L'intention est que vous devriez être en mesure d'interpréter un code long encodage des étiquettes de W comme une coupe de H . Rappelons que pour encoder des σ ∈ Σ avec le code long, vous utilisez une fonction booléenne f : { - 1 , 1 } Σ → { - 1 , 1 $H$$W$$2^m$$x \in \{-1, 1\}^\Sigma$$W$$H$$\sigma \in \Sigma$$f\colon \{-1, 1\}^\Sigma \to \{-1, 1\}$; c'est en particulier la fonction dictateur . Produisons une coupe S ∪ T (c'est-à-dire bi-partition des sommets) à partir du codage de code long comme suit. Si w ∈ W a une étiquette codée par la fonction booléenne f , allez dans le nuage de sommets en H correspondant à w , et mettez en S tous les sommets du nuage étiquetés par quelques x pour lesquels f ( x ) = 1 . Tous les autres vont à $f(x) = x_\sigma$$S\cup T$$w \in W$$f$$H$$w$$S$$x$$f(x) = 1$$T$. Vous pouvez le faire en arrière pour assigner des fonctions booléennes à tous basée sur une coupe de H .$w \in W$$H$

Pour que la réduction fonctionne, vous devez être en mesure de dire seulement en regardant la valeur d'une coupe $S\cup T$ si les fonctions booléennes correspondant à la coupe sont proches d'un codage de code long d'une attribution d'étiquettes à qui satisfait un grand nombre de contraintes UG de G . Donc , la question est ce que les informations que nous recevons de la valeur d'une coupe S ∪ T . Considérons deux sommets a avec l'étiquette x dans le nuage correspondant à w et b avec l'étiquette y dans le nuage correspondant à w $W$$G$$S \cup T$$a$$x$$w$$b$$y$$w'$(dans la réduction, nous ne regardons que , w ′ dans différents nuages). Nous avons dit que la coupe peut être utilisée pour dériver des fonctions booléennes f w et f w ′ . Maintenant, s'il y a une arête ( a , b ) dans H , alors ( a , b ) est coupé si et seulement si f w ( x ) ≠ f w ′ ( y $w$$w'$$f_w$$f_{w'}$$(a,b)$$H$$(a, b)$$f_w(x) \neq f_{w'}(y)$. Par conséquent, utiliser uniquement la valeur d'une coupure pour dire si les fonctions booléennes induites sont "bonnes" revient à avoir un test qui, étant donné les fonctions booléennes , ne demande que la fraction d'une liste spécifiée des paires ( ( w , x ) , ( w ′ , y ) ) nous avons f w ( x ) ≠ f w ′ ( y ) .$\{f_w\}_{w \in W}$$((w, x), (w', y))$$f_w(x) \neq f_{w'}(y)$

En d'autres termes, chaque fois que Ryan dit dans les notes "tester si ", ce qu'il veut vraiment dire "en H , ajouter un bord entre le sommet dans le nuage de w étiqueté par x et le sommet dans le nuage de w ' marqué par y ". C'est-à-dire pour tout v ∈ V , tous les deux de ses voisins w , w ′ et tous les x , y ∈ { - 1 , 1 $f_w(x) \neq f_{w'}(y)$$H$$w$$x$$w'$$y$$v\in V$$w, w'$ , inclure l'arête entre le sommet dans le nuage de w étiqueté par x ∘ π v , w et le sommet dans le nuage de w ′ étiqueté par y ∘ π v , w ′ , et affecter le poids de l'arête ( ( 1 - ρ ) / 2 ) d ( ( 1 + ρ ) / 2 ) n - d où d est la distance de Hamming entre$x,y \in \{-1, 1\}^n$$w$$x\circ \pi_{v,w}$$w'$$y \circ \pi_{v,w'}$$(({1-\rho})/{2})^d(({1+\rho})/{2})^{n-d}$$d$$x$et . De cette façon, la valeur d'une coupe divisée par le poids total du bord est exactement égale à la probabilité de réussite du test.$y$