Czy ktoś zna pracę formalnie analizującą "mniej sprytną" wersję FRI, w której zapytania są wybierane niezależnie na każdym poziomie? (Kosztem 2x długości dowodu).

W szczególności dwa przykłady, które podajesz jako złe wyniki, nie są problematyczne, moim zdaniem - tzn. wystarczy, że fri wykryje, czy *zacząłeś* daleko od kodowego słowa, nie sądzę, żebyś się martwił, czy kodowe słowo zostało zmienione, czy skończyłeś daleko od kodowego słowa (co tak naprawdę zostanie wychwycone, ponieważ weryfikator odczytuje całe słowo na końcowej warstwie)

@GuilleAngeris Przy okazji, czy założenie w tym artykule jest takie, że jesteśmy w UDR?

@UHaboeck @GiacomoFenzi Moja motywacja polegała po prostu na poprawieniu artykułu z najmniejszą "odległością edycyjną". W szczególności chciałem, aby złe zdarzenia, które były tylko składaniem, nie zmniejszały odległości, a nie nieco bardziej złożone złe zdarzenie w MCA.

@UHaboeck @GiacomoFenzi Napraw to, ponieważ korzystało z wadliwej analizy z tego artykułu o lukach przed bliskością.

@UHaboeck @GiacomoFenzi Tzn. jednym z moich spostrzeżeń dzisiaj było to, że dla niezależnego zapytania FRI możesz analizować tylko za pomocą "zwykłego" CA, a nie ważonego lub wzajemnego. Ale zrobiłem to tak szybko, że może jutro zjem skromne ciasto :)

@UHaboeck @GiacomoFenzi A na dodatek.. musisz za każdym razem wybierać losową warstwę do sprawdzenia, aby uzyskać najlepszy błąd graniczny, zamiast zapytywać na wszystkich warstwach. To ma związek z (1-delta/t)^t będącym większym niż 1-delta dla (przynajmniej niektórych wartości) t>1

@aszepieniec *obie mamy literówkę - to (1-1/r)^r, a nie (1-r)^r

@aszepieniec *Pierwsze `to` odnosi się do tweeta powyżej, a drugie `to` do powiązanego tweeta :)

@aszepieniec Dokładniej mówiąc, wydaje się, że dla danej odległości delta możemy ograniczyć prawdopodobieństwo sukcesu niezależnego zapytania FRI do e^{-delta}, podczas gdy dla regularnego FRI możemy uzyskać 1-delta, co jest np. mniejsze o ~0.1 dla delta=1/2