Alguém está ciente de um artigo que analisa formalmente a versão "menos inteligente" do FRI, onde as consultas são escolhidas independentemente em cada camada? (À custa de 2x no comprimento da prova).

em particular, os dois exemplos que você dá de um resultado ruim não são problemáticos, eu acho - ou seja, você só precisa que o fri detecte se você *começou* longe de uma palavra-chave, não acho que você se importe se a palavra-chave foi trocada, ou se você terminou longe de uma palavra-chave (o que na verdade será detectado porque o verificador lê a palavra inteira na camada final)

@GuilleAngeris A propósito, a suposição neste artigo é que estamos em UDR?

@UHaboeck @GiacomoFenzi A minha motivação era apenas corrigir o artigo com a menor "distância de edição". Em particular, eu queria manter os eventos negativos, apenas o fato de dobrar não diminuiu a distância, em vez do evento negativo ligeiramente mais complexo no MCA.

@UHaboeck @GiacomoFenzi Corrija, pois estava a usar a análise defeituosa deste artigo sobre lacunas de proximidade prévias.

@UHaboeck @GiacomoFenzi Ou seja, uma das minhas percepções mais cedo hoje foi que para a consulta independente FRI, você pode analisar apenas com CA "regular" em vez de ponderada ou mútua. Mas fiz isso tão rápido que talvez eu tenha que engolir o orgulho amanhã :)

@UHaboeck @GiacomoFenzi E além disso... você precisa escolher uma camada aleatória para verificar a cada vez para obter o melhor limite de erro, em vez de consultar todas as camadas. Isso tem a ver com (1-delta/t)^t sendo maior que 1-delta para (pelo menos alguns valores de) t>1

@aszepieniec *nós dois temos um erro de digitação - é (1-1/r)^r e não (1-r)^r

@aszepieniec *O primeiro `isto` refere-se ao tweet acima, e o segundo isto ao tweet vinculado :)

@aszepieniec Mais precisamente, parece que para uma distância delta dada, podemos limitar a probabilidade de sucesso da consulta ind FRI por e^{-delta}, enquanto que para o FRI regular podemos obter 1-delta, que é, por exemplo, menor em ~0.1 para delta=1/2