Journal article · 2026 · Open access
STIR: Reed–Solomon Proximity Testing with Fewer Queries
Journal of the ACM · Published 16 October 2026 · DOI 10.1145/3858414
In brief
“STIR: Reed–Solomon Proximity Testing with Fewer Queries” is a 2026 journal article by Gal Arnon and 3 co-authors, published in Journal of the ACM. OpenAlex counts 1 citations as of 17 November 2026. It is open access under a CC BY-NC-ND licence: the full text is free to read at Infoscience (Ecole Polytechnique Fédérale de Lausanne).
- Citations
- 1
- Most cited in
- 2026 (1)
- Field-weighted impact
- 1.69
- References
- 25
- Authors
- 4
Abstract
We present STIR (Shift To Improve Rate), an interactive oracle proof of proximity (IOPP) for Reed–Solomon codes that achieves the best known query complexity of any concretely efficient IOPP for this problem. For λ bits of security, STIR has query complexity O (log d + λ · log logd ), while FRI, a popular protocol, has query complexity O ( λ · log d ) (including variants of FRI based on conjectured security assumptions). STIR relies on a new technique for recursively improving the rate of the tested Reed–Solomon code. We provide an implementation of STIR compiled to a SNARK. Compared to a highly-optimized implementation of FRI, STIR achieves an improvement in argument size that ranges from 1.25 × to 2.46 × depending on the chosen parameters, with similar prover and verifier running times. For example, in order to achieve 128 bits of security for degree 2 26 and rate 1/4, STIR has argument size 114 KiB, compared to 211 KiB for FRI.
Cite this paper
Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.
APA 7
Arnon, G., Chiesa, A., Fenzi, G., & Yogev, E. (2026). STIR: Reed–Solomon Proximity Testing with Fewer Queries. Journal of the ACM. https://doi.org/10.1145/3858414
MLA 9
Arnon, Gal, et al. “STIR: Reed–Solomon Proximity Testing with Fewer Queries.” Journal of the ACM, 2026. https://doi.org/10.1145/3858414.
Chicago
Arnon, Gal, Alessandro Chiesa, Giacomo Fenzi, and Eylon Yogev. 2026. “STIR: Reed–Solomon Proximity Testing with Fewer Queries.” Journal of the ACM. https://doi.org/10.1145/3858414.
Harvard
Arnon, G. et al. (2026) ‘STIR: Reed–Solomon Proximity Testing with Fewer Queries’, Journal of the ACM. doi:10.1145/3858414.
IEEE
G. Arnon, A. Chiesa, G. Fenzi, and E. Yogev, “STIR: Reed–Solomon Proximity Testing with Fewer Queries,” Journal of the ACM, 2026, doi: 10.1145/3858414.
BibTeX
@article{arnon2026stir,
title = {{STIR: Reed–Solomon Proximity Testing with Fewer Queries}},
author = {Arnon, Gal and Chiesa, Alessandro and Fenzi, Giacomo and Yogev, Eylon},
journal = {Journal of the ACM},
year = {2026},
doi = {10.1145/3858414},
url = {https://doi.org/10.1145/3858414}
}
Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)
Topic and keywords
Physical Sciences › Computer Science › Computer Networks and Communications › Cryptography and Data Security
- Reed-Solomon codes
- query complexity
- FRI
- snarks
- STIR
Work with this paper
Most-cited papers in Computer Science
- ImageNet classification with deep convolutional neural networksAlex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton · Communications of the ACM · 2017 · 114,726 citations
- Long Short-Term MemorySepp Hochreiter, Jürgen Schmidhuber · Neural Computation · 1997 · 109,097 citations
- A Mathematical Theory of CommunicationClaude E. Shannon · Bell System Technical Journal · 1948 · 91,736 citations
- Deep learningYann LeCun, Yoshua Bengio, Geoffrey E. Hinton · Nature · 2015 · 90,226 citations
- Faster R-CNN: Towards Real-Time Object Detection with Region Proposal NetworksShaoqing Ren, Kaiming He, Ross Girshick and 1 more · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2016 · 74,143 citations
Questions about this paper
How do I cite this paper in APA style?
Arnon, G., Chiesa, A., Fenzi, G., & Yogev, E. (2026). STIR: Reed–Solomon Proximity Testing with Fewer Queries. Journal of the ACM. https://doi.org/10.1145/3858414
How many times has this paper been cited?
1 times, according to OpenAlex on 17 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.
Is this paper free to read?
Yes. It is open access at Infoscience (Ecole Polytechnique Fédérale de Lausanne): sign in and open the full text from this page.
Who wrote this paper?
Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, Eylon Yogev.
What is the DOI of this paper?
10.1145/3858414, permanently at https://doi.org/10.1145/3858414. Sign in and open it from this page.
Bibliographic data from OpenAlex (CC0), last checked 17 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.