¿Alguien está al tanto de un artículo que analice formalmente la versión "menos inteligente" de FRI donde las consultas se eligen de forma independiente en cada capa? (A costa de 2x en la longitud de la prueba).

en particular, los dos ejemplos que das de un mal resultado no son problemáticos, creo. Es decir, solo necesitas que fri detecte si *comenzaste* lejos de una palabra clave, no creo que te importe si la palabra clave fue cambiada o si terminaste lejos de una palabra clave (lo cual, de hecho, será detectado porque el verificador lee toda la palabra en la capa final).

@GuilleAngeris Por cierto, ¿es la suposición en este documento que estamos en UDR?

@UHaboeck @GiacomoFenzi Mi motivación era simplemente corregir el documento con la menor "distancia de edición". En particular, quería mantener los eventos negativos, ya que simplemente doblar no disminuyó la distancia, en lugar del evento negativo ligeramente más complejo en MCA.

@UHaboeck @GiacomoFenzi Corrige porque estaba utilizando el análisis defectuoso de este artículo sobre brechas de proximidad previa.

@UHaboeck @GiacomoFenzi Es decir, una de mis observaciones de hoy fue que para la consulta independiente FRI, puedes analizar solo con CA "regular" en lugar de ponderada o mutua. Pero lo he hecho tan rápido que tal vez mañana tenga que comerme mis palabras :)

@UHaboeck @GiacomoFenzi Y además de eso... necesitas elegir una capa aleatoria para verificar cada vez para obtener el mejor límite de error, en lugar de consultar en todas las capas. Esto tiene que ver con (1-delta/t)^t siendo mayor que 1-delta para (al menos algunos valores de) t>1

@aszepieniec *ambos tenemos un error tipográfico - es (1-1/r)^r no (1-r)^r

@aszepieniec *El primer `esto` se refiere al tweet anterior, y el segundo `esto` al tweet vinculado :)

@aszepieniec Más precisamente, parece que para una distancia delta dada podemos acotar la probabilidad de éxito de la consulta ind FRI por e^{-delta}, mientras que para el FRI regular podemos obtener 1-delta, que es, por ejemplo, menor en ~0.1 para delta=1/2