Sample-Preserving Search-to-Decision Reduction for Noisy Linear Equations over Large Moduli

Andrej Bogdanov, Kel Zin Tan, Prashant Nalini Vasudevan

The Noisy Linear Equations problem involves finding the solution to a random linear system over a finite field given noisy evaluations. This is a generalisation of various learning…