Guo Yu retweetledi
Sitting on the shoulders of giants, I am glad to announce the following paper with Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, and Shubhangi Saraf:
eccc.weizmann.ac.il/report/2025/16…
On the one hand, we improve the existing decoder analysis from Ben-Sasson, Carmon, Ishai, Kopparty and Saraf (BCIKS 2020), reducing it to an O(n) soundness error for correlated agreement up to the Johnson radius.
In practice, it shows that degree 4 extensions of a 31 bit prime field (like M31, Babybear or Koalabear) are sufficient for FRI up to that radius, in many applications, considering that you are willing to grind.
On the other hand, we provide additional counter examples that question the proximity gaps conjecture as written. Notably, over binary fields one cannot expect an O(n) error already *at* Johnson radius, rather a quadratic one.
In general, proximity gaps stop at the distance where we have more than field size many proximates, meaning that we have to respect small gap to capacity. (See also the recent work of Crites and Stewart, as well as Diamond and Gruen.)
English
