Qualcuno è a conoscenza di un documento che analizza formalmente la versione "meno intelligente" di FRI in cui le query vengono scelte in modo indipendente a ciascun livello? (A scapito di 2x nella lunghezza della prova).

in particolare i due esempi che dai di un esito negativo non sono problematici, penso - cioè, hai solo bisogno che fri rilevi se hai *iniziato* lontano da una parola chiave, non credo ti importi se la parola chiave è stata cambiata, o se sei finito lontano da una parola chiave (cosa che in realtà verrà rilevata perché il verificatore legge l'intera parola all'ultimo strato)

@GuilleAngeris A proposito, l'assunzione in questo documento è che siamo in UDR?

@UHaboeck @GiacomoFenzi La mia motivazione era semplicemente quella di correggere il documento con la "distanza di modifica" più piccola. In particolare, volevo mantenere i cattivi eventi in cui il semplice piegamento non diminuiva la distanza, piuttosto che il cattivo evento leggermente più complesso in MCA.

@UHaboeck @GiacomoFenzi Risolvi perché stava utilizzando l'analisi difettosa di questo documento sui gap di prossimità pre.

@UHaboeck @GiacomoFenzi Cioè, una delle mie intuizioni di oggi era che per la query indipendente FRI, puoi analizzare semplicemente con CA "normale" piuttosto che pesata o mutua. Ma l'ho fatto così in fretta che forse domani dovrò mangiarmi il cappello :)

@UHaboeck @GiacomoFenzi E oltre a questo.. devi scegliere uno strato casuale da controllare ogni volta per ottenere il miglior limite di errore, piuttosto che interrogare tutti gli strati. Questo ha a che fare con (1-delta/t)^t che è maggiore di 1-delta per (almeno alcuni valori di) t>1

@aszepieniec *abbiamo entrambi un errore di battitura - è (1-1/r)^r non (1-r)^r

@aszepieniec *Il primo `questo` si riferisce al tweet sopra, e il secondo questo al tweet linkato :)

@aszepieniec Più precisamente, sembra che per una certa distanza delta possiamo limitare la probabilità di successo della query ind FRI a e^{-delta}, mentre per il FRI regolare possiamo ottenere 1-delta che è, ad esempio, più piccolo di ~0.1 per delta=1/2