Кто-нибудь знает о статье, формально анализирующей "менее умную" версию FRI, где запросы выбираются независимо на каждом уровне? (С потерей 2x в длине доказательства).

в частности, два примера, которые вы приводите о плохом результате, не являются проблемными, я думаю - т.е. вам просто нужно, чтобы fri определил, если вы *начали* далеко от кодового слова, я не думаю, что вам важно, было ли кодовое слово переключено, или вы закончили далеко от кодового слова (что на самом деле будет поймано, потому что проверяющий читает все слово на финальном слое)

@GuilleAngeris Кстати, предположение в этой статье заключается в том, что мы находимся в UDR?

@UHaboeck @GiacomoFenzi Моя мотивация заключалась в том, чтобы исправить статью с наименьшим "редакционным расстоянием". В частности, я хотел сохранить плохие события, просто складывая, чтобы не уменьшать расстояние, а не немного более сложное плохое событие в MCA.

@UHaboeck @GiacomoFenzi Исправьте, потому что использовался ошибочный анализ из этой статьи о предельных разрывах.

@UHaboeck @GiacomoFenzi То есть, одно из моих наблюдений сегодня заключалось в том, что для независимого запроса FRI вы можете анализировать просто с помощью "обычного" CA, а не взвешенного или взаимного. Но я сделал это так быстро, что, возможно, завтра мне придется смириться с этим :)

@UHaboeck @GiacomoFenzi И вдобавок к этому... вам нужно каждый раз выбирать случайный слой для проверки, чтобы получить наилучшую границу ошибки, а не запрашивать на всех слоях. Это связано с (1-дельта/t)^t больше, чем 1-дельта для (по крайней мере, некоторых значений) t>1

@aszepieniec *у нас обоих опечатка - это (1-1/r)^r, а не (1-r)^r

@aszepieniec *Первый `this` относится к твиту выше, а второй `this` к связанному твиту :)

@aszepieniec Более точно, кажется, что для заданного расстояния дельта мы можем ограничить вероятность успеха независимого запроса FRI по формуле e^{-дельта}, в то время как для обычного FRI мы можем получить 1-дельта, что, например, меньше примерно на 0.1 при дельта=1/2