Have number theoretic functions such as Gauss sums been studied from a complexity view point? Where can I get a good introduction into complexity of Gauss sum estimation (beyond the quadratic case)?

Actually I was looking for something more than the answers given. It is known Gauss sums have a random walk behavior than is exploited in designing low-correlation sequences. Also Montogomery's conjecture provides a tighter bound than the Weil bounds of Deligne under the assumption of random behavior (deeper exposition in the book by Katz and Sarnak - the material of which I am not familiar). I was actually curious whether such randomness has been utilized in computer science. It seems very possible there are uses.

  • $\begingroup$ You are now asking a quite different question... $\endgroup$ Jul 27, 2011 at 9:49
  • $\begingroup$ @Martin I thought the questions are related? $\endgroup$
    – v s
    Jul 27, 2011 at 16:00
  • $\begingroup$ @Martin I think some complexity classes do include randomness in their definitions. $\endgroup$
    – v s
    Jul 28, 2011 at 2:18

2 Answers 2


See Efficient Quantum Algorithms for Estimating Gauss Sums by Wim van Dam and Gadiel Seroussi.

They have a nice introduction to the computational problem of estimating Gauss sums over finite fields and finite rings. They carefully explain how the computational problem is specified, how the characters are specified in the input and what the input size is.

They show how to estimate the phase of a Gauss sum to inverse polynomial accuracy in polynomial time on a quantum computer. They then show that this problem is classically hard assuming discrete log is hard.


Cai, Chen, Lipton, and Lu have recently proved a dichotomy theorem on tractable exponential sums. The quadratic case is in P, whereas the cubic case is already #P-complete.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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