Transformación Beigel-Tarui de cricuits ACC

14

Estoy leyendo el apéndice sobre los límites inferiores de ACC para NEXP en el libro Arora and Barak's Computational Complexity . http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf Uno de los lemas fundamentales es una transformación de la circuitos a lo largo de los polinomios multilineales enteros con grado polilogarítmico y coeficientes quasipolynomial, o equivalentemente, la clase de circuito , que es la clase de profundidad de dos circuitos con muchas puertas AND cuasipolinomialmente en su nivel inferior con entrada de entrada poligarrítmica y una puerta simétrica en el nivel superior. S Y M +ACC0SYM+

En el apéndice del libro de texto, esta transformación tiene tres pasos, suponiendo que el conjunto de compuertas consta de OR, mod , mod 3 y la constante 1 . El primer paso es reducir el abanico de las compuertas OR al orden pollogarítmico.3 1231

Usando el Lema de aislamiento Valiant-Vazirani, los autores obtienen que dada una puerta OR sobre 2k entradas de la forma OR(x1,...,x2k) , si recoger h a ser una función hash independiente pairwise, a partir de [2k] a {0,1} , entonces para cualquier distinto de cero x{0,1}2k , con probabilidad de al menos 1/(10k) mantendrá que Σi:h(i)=1ximod 2 .

¿No es la probabilidad de Σi:h(i)=1ximod 2 al menos 1/2 ? Parece que 1/10k es un límite inferior débil.

El segundo paso es pasar a las puertas aritméticas y empujar las multiplicaciones hacia abajo. En este paso, transformaremos los circuitos booleanos con una cadena de entrada binaria dada en un circuito aritmético con una entrada entera.

Aquí notan que se reemplaza con , y se reemplaza con usando el pequeño teorema de Fermat.1 - x 1 x 2x k M O D p ( x 1 , . . . , X k ) ( Σ i = 1 , . . . , K x i ) p - 1OR(x1,...,xk)1x1x2xkMODp(x1,...,xk)(Σi=1,...,kxi)p1

¿Por qué este reemplazo da un circuito equivalente ?SYM+

echuly
fuente
3
No entiendo la expresión que sigue "con una probabilidad de al menos 1 / (10k) mantendrá que ..." ¿Te falta un signo igual? Además, ¿podría citar el número de página donde aparece esta prueba?
Robin Kothari

Respuestas:

10

¿No es la probabilidad de al menos 1/2? Parece que es un límite inferior débil.1 / ( 10 k )Σi:h(i)=1ximod 2=11/(10k)

De hecho, la respuesta es no. (Sería que tiene una probabilidad de al menos , si estuviéramos trabajando con un - familia hash sesgada, y de hecho el uso de funciones hash imparcial proporciona una manera de mejorar los parámetros de la construcción, pero la independencia por pares no es necesariamente imparcial).1 / 2 - varepsilon varepsilon varepsilonΣi:h(i)=1ximod 2=11/2εεεε

Parece que les falta un paso adicional aquí. Para aplicar Valiant-Vazirani directamente, también deberías elegir aleatoriamente el rango de la función hash. En lugar de elegir aleatorio independiente de pares , parece que debería elegir random y luego elegir random independiente de pares . (Aquí estoy usando deliberadamente la declaración de Valiant-Vazirani de Arora-Barak, que se encuentra en la página 354.) Sea el número de . Valiant-Vazirani dice que cuando has elegido modo que , entonces la probabilidad de que{ 2 , , k + 1 } h : [ 2 k ] { 0 , 1 } s x i = 1 2 - 2s 2 - 1 Σ i : h ( i ) =h:[2k]{0,1}{2,,k+1}h:[2k]{0,1}sxi=122s211 /Σi:h(i)=1xi=1 (¡sobre los enteros!) Es al menos .1/8

Por lo tanto, al elegir random y elegir randomndom pairwise , entonces tiene una probabilidad de al menos que . Para simular la elección aleatoria de en el circuito, simplemente puede tomar el sobre todos los posibles (su número es logarítmico en , después de todo), por lo que la probabilidad de éxito se convierte en al menos nuevamente. Entonces, en lugar de tener funciones hash con rango , querrásh : [ 2 k ] { 0 , 1 } 1 / ( 8 k ) Σ i : h ( i ) = 1 x i mod  2 = 1 O R 2 k 1 / 8 O ( k log s ) { 0 , 1 } O ( k )h:[2k]{0,1}1/(8k)Σi:h(i)=1ximod 2=1OR2k1/8O(klogs){0,1}O(k)diferentes conjuntos de funciones hash (cada conjunto tiene un rango diferente), con funciones hash en cada conjunto.O(logs)

¿Por qué este reemplazo da un circuito SYM + equivalente?

Un circuito SYM de AND (es decir, SYM +) de tamaño es esencialmente equivalente a tener un polinomio multivariado con a lo sumo monomios , una tabla de búsqueda , y computación . (Por ejemplo, se puede encontrar una prueba en Beigel-Tarui). La intuición es que cada monomio en es una puerta AND, es la puerta SYM. Digo "esencialmente equivalente" porque el polinomio multilinealKh:{0,1}n{0,,K}Kg:{0,,K}{0,1}g(h(x1,,xn))fghtambién podría tener coeficientes negativos para algunos términos, y los coeficientes negativos obviamente no son implementables en SYM de AND. Pero afirmo (y Beigel y Tarui afirman) que esto no es un problema. Piénsalo :)

Ryan Williams
fuente