Say I have a polynomial over $Q$. Let it be given in the form of arithmetic circuit family ${C_n}$. The randomised poly time algorithm evaluates the polynomial at a random point. What if the number of bits required for the intermediate calculations is too high i.e How can we guarantee that the evaluation does not require more than polynomial bits (polynomial in the size of the circuit) ?

  • $\begingroup$ Please define the question more precisely. What field are you working over? $\mathbb{Z}/p\mathbb{Z}$? $\mathbb{Q}$? What research have you done? This is covered in standard resources on polynomial identity testing. $\endgroup$ – D.W. Feb 21 '15 at 7:00
  • $\begingroup$ I saw a few resources. In all of those, there was this assumption that the polynomial can be evaluated at any given point effeciently. But still, you are right. I should have done more research. $\endgroup$ – Gaganpreet Feb 21 '15 at 8:14

If you're working over $\mathbb{Z}/p\mathbb{Z}$, you don't have to do anything: the intermediate results can't get larger than $p$.

If you're working over $\mathbb{Z}$, the standard trick is to pick a random $k$-bit prime $p$ and then reduce everything modulo $p$, so you are effectively working over $\mathbb{Z}/p\mathbb{Z}$. One can show that the probability of getting a wrong answer using this method is exponentially small in $k$ (using the prime number theorem).

If you're working over $\mathbb{Q}$, you can reduce this to working over $\mathbb{Z}$ by clearing all fractions.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.