Does the numerical algebraic geometry method work in the finite fields? I am working on this method to find a solution for a low-degree proximity testing problem.
Would you please guide me how they work in the finite fields?
Clarification: Consider the $d$ low-degree proximity testing problem for Reed Solomon codes (RPT). Informally, we can define it as below:
The RPT problem assumes a verifier has oracle access to $f$ (as the evaluation of some points by calculating the RS code i.e it is a polynomial in the finite field) and to auxiliary information like a PCP (Polynomially Checkable Proof) of Proximity (PCPP) or an IOP (Interactive Oracle Proof) of proximity (IOPP); the verifier’s task is to distinguish with high probability and with a small number of queries to $f$ and the auxiliary PCPP/IOPP oracle(s), between the cases:
- that $f$ is a codeword of $RS[F,S,\rho]$; and the case that
- $f$ is $δ-$far from all codewords of $ RS[F,S,\rho]$ in relative Hamming distance.
The existing solutions such as LINK used some techniques including Fast Fourier Transform and also you can find more information about IOP.