On tractable exponential sums

DOI10.1007/978-3-642-14553-7_16MaRDI QIDQ3587346zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Xi Chen, Richard J. Lipton, Pinyan Lu

Publication date 7 September 2010

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.2632

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We consider the problem of evaluating certain exponential sums. These sums take the form $su{m}_{x_1,\mathrm{...},x_{n}in{Z}_N}{e}^{f(x_1,\mathrm{...},x_n)2pii/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.

Recommendations

• Complexity of counting CSP with complex weights
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• Graph homomorphisms with complex values: a dichotomy theorem
• The complexity of partition functions
• Automata, Languages and Programming

Cited in

(6)

• Classical simulation of quantum circuits by half Gauss sums
• scientific article; zbMATH DE number 5905155 (Why is no real title available?)
• scientific article; zbMATH DE number 16337 (Why is no real title available?)
• The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
• FKT is not universal -- a planar holant dichotomy for symmetric constraints
• Counting solutions to polynomial systems via reductions

This page was built for publication: On tractable exponential sums

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587346)