¿Reducción de error determinista, estado del arte?

12

Suponga que uno tiene un algoritmo aleatorio (BPP) usa bits de aleatoriedad. Las formas naturales de amplificar su probabilidad de éxito a , para cualquier elegido , sonAr1δδ>0

  • Ejecuciones independientes + voto mayoritario: ejecute independientemente veces, y obtenga el voto mayoritario de los resultados. Esto requiere bits de aleatoriedad, y explota el tiempo de ejecución por un factor .AT=Θ(log(1/δ)rT=Θ(rlog(1/δ))T=Θ(log(1/δ))
  • Ejecuciones independientes por pares + Chebyshev: ejecuta "por pares independientemente" veces, y compara con un umbral Esto requiere bits de aleatoriedad , y explota el tiempo de ejecución por un factor .AT=Θ(1/δ)rT=Θ(r/δ)T=Θ(1/δ)

Karp, Pippenger y Sipser [1] (aparentemente; no pude poner mis manos en el papel en sí, es una cuenta de segunda mano) proporcionaron enfoques alternativos basados ​​en expansores regulares fuertes: esencialmente, vea los nodos del expansor como las semillas al azar. Elija un nodo aleatorio del expansor utilizando los bits aleatorios , y luego2rr

  • haga una caminata aleatoria corta de longitud desde allí, y ejecute en las semillas correspondientes a los nodos en el camino, antes de tomar un voto mayoritario. Esto requiere bits de aleatoriedad , y explota el tiempo de ejecución por un factor .T=Θ(log(1/δ))ATr+T=r+Θ(log(1/δ))T=Θ(log(1/δ))

  • ejecute en todos los vecinos del nodo actual (o, más generalmente, todos los nodos dentro de una distancia del nodo actual) antes de tomar un voto mayoritario. Esto requiere bits de aleatoriedad, y explota el tiempo de ejecución por un factor , donde es el grado (o para la distancia- vecindad. Si configura bien los parámetros, esto termina costando aquí.AcrT=dddccT=poly(1/δ)

Estoy interesado en la última viñeta, que corresponde a la reducción determinista de errores. ¿Ha habido alguna mejora después de [1], reduciendo la dependencia de en ? ¿Cuál es el mejor actualmente posible: para el cual ? ? (¿Para ? Para ?)Tδ1/δγγ>1γ>0BPPRP

Nota: También estoy (muy) interesado en lugar de . Como se introdujo en [2], la construcción relevante ya no son expansores, sino dispersores (ver, por ejemplo, estas notas de Ta-Shma, especialmente en la Tabla 3). Sin embargo, no pude encontrar los límites correspondientes para la amplificación determinista (ni un solo bit más aleatorio que el permitido ), ni (más importante) cuáles son las construcciones de dispersor explícito de vanguardia para el rango relevante de parámetros .RPBPPr


[1] Karp, R., Pippenger, N. y Sipser, M., 1985. Una compensación de aleatoriedad temporal . En AMS Conference on Probabilistic Computational Complexity (Vol. 111).

[2] Cohen, A. y Wigderson, A., 1989, octubre. Dispersores, amplificación determinista y fuentes aleatorias débiles. En el 30º Simposio anual sobre fundamentos de la informática (pp. 14-19). IEEE

Clemente C.
fuente
Mi comprensión es la siguiente (principalmente en las notas de clase antes mencionadas de Ta-Shma , las de van Melkebeek y las de Cynthia Dwork . Por lo que puedo decir, los dispersores son excelentes para amplificar exponencialmente con pocos bits aleatorios más , pero no si hay 0 bits adicionales de aleatoriedad.
Clement C.
(si uno está dispuesto a usar estos pocos bits adicionales, entonces la conferencia de Ta-Shma tiene un conjunto muy completo de tablas de resumen). Sin aleatoriedad adicional, el enfoque BPP / RP basado en expansor parece ser el único (ver las notas de van Melkebeek para BPP, Dwork para la variante RP: ambos son muy similares y se basan en el documento [1], de los cuales I no se pudo encontrar un pdf directo). Ninguno parece dar un límite explícito al grado del polinomio en , ya que depende del grado y la expansión del gráfico expansor. poly(1/δ)
Clement C.
Será al menos lineal en : pero ¿qué será para las construcciones (actuales) más conocidas de gráficos expansores? En realidad, incluso para construcciones probabilísticas? 1/δ
Clement C.
También es relevante (pero no responde a la pregunta específica): Sección 3.5.4, y la Sección 4 (Problema 4.6) de la Salil Vadhan pseudoaleatoriedad .
Clement C.

Respuestas:

3

¿Las notas de clase de van Melkebeek ya no dan un límite ? El límite allí es como máximo y podemos obtener utilizando las construcciones existentes.O(1/δ)λO(δ)λ=O(1/d)

En las notas de clase de Dwork también, la condición requerida es que la expansión sea para algo de constante (mirar puntos en la distancia c es esencialmente usar potencia para mejorar la expansión). Que nuevamente se puede obtener con grado .C/δCO(1/δ)

Quizás haya un límite inferior de en la cantidad de ejecuciones requeridas.Ω(1/δ)

invitado
fuente
Ya veo, déjame reformularlo para confirmar que lo entiendo bien. Dejando que sea ​​la probabilidad de error original, si tenemos un expansor espectral de grado en nodos con un segundo valor propio (donde es explícito, diferente para RP y BPP), entonces tenemos una explosión en el tiempo de ejecución de . Entonces, si tenemos una familia de expansores explícitos con para todo , , todo lo que necesitamos es para obligado a estar satisfecho. α>0dR=2rλδCαCαd(N,d)λC/dNdd=Oα(1/δ)
Clemente C.
Por ejemplo, se sabe que existen gráficas de Ramanujan arbitrariamente grandes (de manera constructiva) para cualquier grado tal que sea ​​una potencia principal. ¿Pero tenemos construcciones explícitas de gráficos con para todo (o, digamos, para todo que es una potencia de dos)? (No estoy lo suficientemente informado sobre eso, y el único resultado de ese tipo que pude encontrar es la construcción de Balu-Linial que da y no es muy explícito). dd1λ=O(1/d) nnO((log3d)/d)
Clement C.