2
$\begingroup$

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 exist solutions such as LINK used some techniques including Fast Fourier Transform and also you can find more information about IOP.

$\endgroup$
  • 1
    $\begingroup$ @kodlu: Yes of course. Please take a look on "What is Numerical Algebraic Geometry?" by Jonathan D. Hauenstein et al. $\endgroup$ – Niloofar Nov 16 '18 at 21:45
  • 1
    $\begingroup$ @VadymFedyukovych: Precisely, I am trying to find low-degree proximity testing problem for Reed Solomon codes (RPT). Informally, we can define it as: The RPT problem assumes a verifier has oracle access to f, and to auxiliary information like a PCP of Proximity (PCPP) or an IOP 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 case that f is a codeword of RS[F,S,ρ] and the case that f∈(0,1) is δ-far from all codewords of RS[F,S,ρ] in relative Hamming distance. $\endgroup$ – Niloofar Nov 16 '18 at 21:49
  • 1
    $\begingroup$ @Niloofar, OK, but all this should be in the question statement, in my opinion. $\endgroup$ – kodlu Nov 16 '18 at 22:45
  • 1
    $\begingroup$ please fix any errors in my edit. the last statement about $f$ looks problematic. $\endgroup$ – kodlu Nov 17 '18 at 3:02
  • 1
    $\begingroup$ @kodlu, Thank you so much. It becomes so better than before. I hope it is easy to follow. $\endgroup$ – Niloofar Nov 17 '18 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.