Considere el siguiente modelo: una cadena de n bits r = r 1 ... r n se elige de manera uniforme al azar. A continuación, cada índice i∈ {1, ..., n} se coloca en un conjunto A con probabilidad independiente 1/2. Por último, se permite que un adversario, para cada i∈A separado, a r flip i si se quiere.
Mi pregunta es esta: ¿puede la cadena resultante (llamarla r ') ser utilizada por un algoritmo RP o BPP como su única fuente de aleatoriedad? Suponga que el adversario conoce de antemano todo el algoritmo BPP, la cadena r y el conjunto A, y que tiene un tiempo de cálculo ilimitado. También suponga (obviamente) que el algoritmo BPP no conoce ni las decisiones de cambio del adversario ni A.
Soy consciente de que hay una larga línea de trabajo sobre precisamente este tipo de preguntas, desde el trabajo de Umesh Vazirani sobre fuentes semi aleatorias (un modelo diferente pero relacionado), hasta trabajos más recientes sobre extractores, fusiones y condensadores. ¡Entonces mi pregunta es simplemente si algo de ese trabajo produce lo que quiero! La literatura sobre fuentes aleatorias débiles es tan grande, con tantos modelos sutilmente diferentes, que alguien que sabe de literatura probablemente me puede ahorrar mucho tiempo. ¡Gracias por adelantado!
fuente
¿Se le permite al adversario ver toda la cadena r antes de decidir cómo establecer los bits en A? Si la respuesta es no, entonces esta es una fuente de fijación de bits, que en realidad es determinísticamente extraíble. Es decir, no se requiere semilla verdaderamente aleatoria. Ver, por ejemplo, Kamp y Zuckerman para construcciones de extractores para fuentes de fijación de bits.
Si al adversario se le permite ver el resto de la cadena, todavía adivinaría que es determinísticamente extraíble, pero los modelos son ligeramente diferentes y no sé desde el principio cómo se relacionan. Dado que el conjunto A es aleatorio, en realidad es incluso más amigable que una fuente de fijación de bits, donde el conjunto A puede ser arbitrario.
fuente
Noam tiene razón, por supuesto. Históricamente, la primera simulación de BPP con una fuente de cualquier tasa de entropía constante se dio en mi trabajo "Simulando BPP utilizando una fuente aleatoria débil general". Ahora hay formas más simples de lograr esto e incluso resultados más fuertes.
La extracción determinista de más de un número constante de bits es imposible en su modelo. (Puede obtener una extracción determinista débil de 1 bit simplemente generando el primer bit). Kamp y yo demostramos que es imposible extraer más de un número constante de bits en una fuente general de fijación de bits no inconsciente con una tasa de entropía constante, pero como el conjunto A es aleatorio, esos resultados no se aplican como se indica. Sin embargo, nuestra prueba funcionó eligiendo A al azar de un tamaño fijo t, por lo que al elegir t = .6n, digamos, el resultado de una A uniformemente aleatoria seguirá.
fuente