12 papers
Locality of Curve-Decoding and Improved Proximity Gaps
Rohan Goyal, Venkatesan Guruswami, Yihang Sun +1
Proximity gaps are a property of error correcting codes that arise in the study of Interactive Oracle Proofs (IOPs) and Succinct Non-interactive Arguments of Zero Knowledge (SNARKs…
On Worst-Case Optimal Polynomial Intersection
Yihang Sun, Mary Wootters
The Optimal Polynomial Intersection (OPI) problem is the following: Given sets and evaluation points , find…
Limitations to Computing Quadratic Functions on Reed-Solomon Encoded Data
Keller Blackwell, Mary Wootters
We study the problem of low-bandwidth non-linear computation on Reed-Solomon encoded data. Given an Reed-Solomon encoding of a message vector $\mathbf{f} \in \mathbb{F}_q^k…
Optimization by Decoded Quantum Interferometry
Stephen P. Jordan, Noah Shutty, Mary Wootters +6
Achieving superpolynomial speedups for optimization has long been a central goal for quantum algorithms. Here we introduce Decoded Quantum Interferometry (DQI), a quantum algorithm…
Improved Bounds on Access-Redundancy Tradeoffs in Quantized Linear Computations
Ching-Fang Li, Mary Wootters
Consider the problem of computing quantized linear functions with only a few queries. Formally, given , our goal is to encode as $\mathbf{c…
Efficient List-decoding of Polynomial Ideal Codes with Optimal List Size
Noga Ron-Zewi, S. Venkitesh, Mary Wootters
In a recent breakthrough [BGM23, GZ23, AGL23], it was shown that randomly punctured Reed-Solomon codes are list decodable with optimal list size with high probability, i.e., they a…