7
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ You are now asking a quite different question... $\endgroup$
    – Martin Schwarz
    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

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
8
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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