Una explicación puramente teórica de gráficos de la reducción de Unique Label Cover a Max-Cut

Estoy estudiando la Conjetura de juegos únicos y la famosa reducción a Max-Cut de Khot et al. Desde su artículo y en otras partes de Internet, la mayoría de los autores usan (lo que para mí es) una equivalencia implícita entre la reducción MAX-CUT y la construcción de pruebas particulares para códigos largos. Debido a mi propia falta de claridad sobre esa equivalencia, lucho por seguir este tren de pensamiento.

También parece claro a partir de estas exposiciones que uno podría describir la reducción únicamente en términos de gráficos, pero que por coincidencia o preferencia nadie elige hacerlo de esa manera. Por ejemplo, en estas notas de O'Donnell, insinúa que la prueba de código largo corresponde a una definición natural de los bordes en el gráfico que se está construyendo, pero como no se explica en detalle, esa regla parece depender de la elección de un corte para definir la función booleana que se está probando, y me ha dejado bastante confundido.

Así que le pido a alguien que explique la reducción "solo" gráficamente en teoría. Creo que esto me ayudará a comprender la equivalencia entre los dos puntos de vista.

Déjame ver si puedo aclarar esto, en un nivel alto. Suponga que la instancia de UG es un gráfico bipartito , biyecciones { π e } e ∈ E , donde π e : Σ → Σ , y | Σ | = m . Desea construir un nuevo gráfico H para que si la instancia de UG es 1 - δ satisfactoria, entonces H tiene un corte grande, y si la instancia de UG ni siquiera es δ- satisfactoria, entonces$G = (V \cup W, E)$$\{\pi_e\}_{e \in E}$$\pi_e\colon \Sigma \to \Sigma$$|\Sigma| = m$$H$$1-\delta$$H$$\delta$ solo tiene cortes muy pequeños.$H$

El gráfico contiene, para cada vértice en W , una nube de 2 m puntos, cada uno etiquetado por alguna x ∈ { - 1 , 1 } Σ . La intención es que debe ser capaz de interpretar un código largo codificación de las etiquetas de W como un corte de H . Recuerde que para codificar algunos σ ∈ Σ con el código largo, utiliza una función booleana 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\}$; en particular es la función del dictador . Produzcamos un corte S ∪ T (es decir, bi-partición de los vértices) a partir de la codificación de código largo de la siguiente manera. Si w ∈ W tiene una etiqueta codificada por la función booleana f , vaya a la nube de vértices en H correspondiente a w , y coloque en S todos los vértices en la nube que estén etiquetados por alguna x para la cual f ( x ) = 1 . Todos los demás van a $f(x) = x_\sigma$$S\cup T$$w \in W$$f$$H$$w$$S$$x$$f(x) = 1$$T$. Usted puede hacer esto al revés para asignar funciones booleanas a todos basado en un corte de H .$w \in W$$H$

Para que la reducción funcione, solo$S\cup T$ debe saber al observar el valor de un corte S ∪ T si las funciones booleanas correspondientes al corte están cerca de una codificación de código larga de alguna asignación de etiquetas a que satisface una gran cantidad de las limitaciones de UG G . Entonces la pregunta es ¿qué información que obtenemos del valor de un corte S ∪ T . Considere dos vértices a con etiqueta x en la nube correspondiente a w y b con etiqueta y en la nube correspondiente a w $W$$G$$S \cup T$$a$$x$$w$$b$$y$$w'$(en la reducción solo miramos , w ' en diferentes nubes). Dijimos que el corte se puede usar para derivar funciones booleanas f w y f w ' . Ahora, si hay un borde ( a , b ) en H , entonces ( a , b ) se corta si y solo 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)$. Por lo tanto, usar solo el valor de un corte para determinar si las funciones booleanas que induce son "buenas" es lo mismo que tener una prueba que, dadas las funciones booleanas , solo pregunta qué fracción de alguna lista específica de pares ( ( w , x ) , ( w ′ , y ) ) tenemos f w ( x ) ≠ f w ′ ( y ) .$\{f_w\}_{w \in W}$$((w, x), (w', y))$$f_w(x) \neq f_{w'}(y)$

En otras palabras, cuando Ryan dice en las notas "prueba si ", lo que realmente quiere decir es "en H , agrega un borde entre el vértice en la nube de w etiquetado por x y el vértice en la nube de w ' marcado por y ". Es decir, por cada v ∈ V , cada dos de sus vecinos w , w ′ y cada x , y ∈ { - 1 , 1 $f_w(x) \neq f_{w'}(y)$$H$$w$$x$$w'$$y$$v\in V$$w, w'$ , incluya el borde entre el vértice en la nube de w etiquetado con x ∘ π v , w y el vértice en la nube de w ′ etiquetado con y ∘ π v , w ′ , y asigne el peso del borde ( ( 1 - ρ ) / 2 ) d ( ( 1 + ρ ) / 2 ) n - d donde d es la distancia 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$y . De esta manera, el valor de un corte dividido por el peso total del borde es exactamente igual a la probabilidad de éxito de la prueba.$y$