On Tractable Exponential Sums

Details On Tractable Exponential Sums On Tractable Exponential Sums

2010-05-14

arxiv.org/abs/1005.2632v1

Computer Science

Computational Complexity

Scientific paper

We consider the problem of evaluating certain exponential sums. These sums take the form $\sum_{x_1,...,x_n \in Z_N} e^{f(x_1,...,x_n) {2 \pi i / N}} $, where each x_i is summed over a ring Z_N, and f(x_1,...,x_n) is a multivariate polynomial with integer coefficients. We show that the sum can be evaluated in polynomial time in n and log N when f is a quadratic polynomial. This is true even when the factorization of N is unknown. Previously, this was known for a prime modulus N. On the other hand, for very specific families of polynomials of degree \ge 3, we show the problem is #P-hard, even for any fixed prime or prime power modulus. This leads to a complexity dichotomy theorem - a complete classification of each problem to be either computable in polynomial time or #P-hard - for a class of exponential sums. These sums arise in the classifications of graph homomorphisms and some other counting CSP type problems, and these results lead to complexity dichotomy theorems. For the polynomial-time algorithm, Gauss sums form the basic building blocks. For the hardness results, we prove group-theoretic necessary conditions for tractability. These tests imply that the problem is #P-hard for even very restricted families of simple cubic polynomials over fixed modulus N.

Affiliated with

Also associated with

No associations

Rating

On Tractable Exponential Sums does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Tractable Exponential Sums, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Tractable Exponential Sums will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-240682