Apakah ada yang mengetahui makalah yang secara resmi menganalisis versi FRI yang "kurang pintar" di mana kueri dipilih secara independen di setiap lapisan? (Dengan mengorbankan 2x panjang bukti).

khususnya dua contoh yang Anda berikan tentang hasil yang buruk saya pikir tidak bermasalah - yaitu Anda hanya perlu fri untuk mendeteksi jika Anda *memulai* jauh dari kata kode, saya tidak berpikir Anda peduli jika kata sandi dialihkan, atau Anda berakhir jauh dari kata sandi (yang sebenarnya akan tertangkap karena verifikator membaca seluruh kata di lapisan terakhir)

@GuilleAngeris Btw, apakah asumsi dalam makalah ini bahwa kita berada di UDR?

@UHaboeck @GiacomoFenzi Motivasi saya hanya untuk memperbaiki makalah dengan "jarak edit" terkecil. Secara khusus, saya ingin menjaga peristiwa buruk hanya dengan melipat tidak mengurangi jarak, daripada peristiwa buruk yang sedikit lebih kompleks di MCA.

@UHaboeck @GiacomoFenzi Perbaiki karena menggunakan analisis yang salah dari makalah celah pra kedekatan ini

@UHaboeck @GiacomoFenzi Yaitu salah satu wawasan saya sebelumnya hari ini adalah bahwa untuk FRI kueri independen, Anda dapat menganalisis hanya dengan CA "regluar" daripada tertimbang atau timbal balik. Tapi saya telah melakukan ini begitu cepat sehingga mungkin saya akan makan pai sederhana besok :)

@UHaboeck @GiacomoFenzi Dan di atas itu.. Anda perlu memilih lapisan acak untuk diperiksa setiap kali untuk mendapatkan terikat kesalahan terbaik, daripada mengkueri semua lapisan. Ini ada hubungannya dengan (1-delta/t)^t lebih besar dari 1-delta untuk (setidaknya beberapa nilai) t>1

@aszepieniec *kita berdua memiliki kesalahan ketik - itu (1-1/r)^are not (1-r)^r

@aszepieniec *'Ini' pertama mengacu pada tweet di atas, dan yang kedua ini untuk tweet yang ditautkan :)

@aszepieniec Lebih tepatnya, tampaknya untuk jarak tertentu delta kita dapat mengikat prob keberhasilan kueri ind FRI dengan e^{-delta}, sedangkan untuk FRI biasa kita bisa mendapatkan 1-delta yang misalnya lebih kecil dengan ~0.1 untuk delta=1/2