Wow! eccc.weizmann.ac.il/report/2…

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/2… 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.)

Actually never took notice of Lev Soukhanov's logup* construction. Such a beautiful idea, to keep looked-up columns entirely virtual, and prove their value at the random point by duality, translating the lookup consistency to the Lagrange function (the eq). eprint.iacr.org/2025/946 Long time ago, I played with same duality to prove the shift on the hypercube. But I did not realise how useful it is for lookups!