It is known (see "Counting curves and their projections" (free version) by von zur Gathen, Karpinski, and Shparlinski) that the problem of finding the number of $\mathbb{F}_q$-rational points on a curve in sparse representation is $\mathsf{\# P}$ complete. Note that the degree of such curve can be exponentially large since sparse representation allows it.

But assume that the degree of a curve is not greater than some polynomial. Can we find the number of $\mathbb{F}_q$-rational points of this curve by using, say, constant iterations of Arthur-Merlin protocol?

  • $\begingroup$ Note that constantly many rounds of AM is the same complexity class as AM... In your question, do you mean that you have a sparse polynomial of bounded degree, or just a degree bound (instead of a sparsity bound)? $\endgroup$ May 23 '16 at 23:25
  • $\begingroup$ @JoshuaGrochow I think both questions are interesting $\endgroup$ May 24 '16 at 9:20

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.