STIR

STIR: Reed–Solomon Proximity Testing with Fewer Queries

This blog-post is a short introduction to our new work: “STIR: Reed-Solomon Proximity Testing with Fewer Queries”. This is joint work with Gal Arnon , Alessandro Chiesa , and Eylon Yogev , and the full version is available on ePrint . Code is also available at WizardOfMenlo/stir . Denote by $\mathsf{RS}[\mathbb{F}, \mathcal{L}, d]$ the Reed-Solomon (RS) code1 over the field $\mathbb{F}$ of rate $\rho = d/|\mathcal{L}|$. Testing proximity to a RS code is the problem of, given oracle access to $f: \mathcal{L} \to \mathbb{F}$, determining whether...

February 2024 · Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, Eylon Yogev

A Time-Space Tradeoff for the Sumcheck Prover

This blog-post is a short introduction to our new work: “A Time-Space Tradeoff for the Sumcheck Prover”. This is joint work with Alessandro Chiesa, Elisabetta Fedele, Andrew Zitek-Estrada, and the full version is available on ePrint. Code accompanying this work can be found at space-efficient-sumcheck. The sumcheck protocol [LFKN92]1 is an interactive protocol between a prover and a verifier that allows a verifier to succinctly check claims of the form $$ \sum_{\mathbf{b} \in \{0, 1\}^n} p(\mathbf{b}) = \gamma \enspace....

February 2024 · Alessandro Chiesa, Elisabetta Fedele, Giacomo Fenzi, Andrew Zitek-Estrada