How well can we do with this variable assignment problem?

Question

Given in this problem is a set of values $0 \le c_{a,b} < n$, where $0 \le a < n$ and $0 \le b < n$.

The problem is to find the following sum as quickly as possible:

$$\sum_{a,b}{c_{a,b}x^a y^b} \bmod n$$

Here $x$ and $y$ are also assumed to be integers modulo $n$.

I'd like to know what the best method/approach is to solving this problem, and what kinds of worst-case behavior we can expect to get the sum.

Are there any similar problems whose solutions may help with this?

SOME NAIVE IDEAS

There are $n^2$ different constants and only $n$ different possible assignments for each $c_{a,b}$, so it seems that grouping some of the coefficients together is the best way to go. However, beyond simple ideas, I'm not sure what will work best. I'm hoping I can get some good suggestions.

MOTIVATION

My motivation for tackling this particular problem is that its solution may help improve the bounds of #3-SAT by some small degree. However, the relation between the two is fairly complicated.

Answer 1

Assuming that the $c_{a,b}$ values appears in a nicely ordered way, you can use Horner's rule to evaluate the polynomial in $O(n^2)$ arithmetic operations. As mentioned by frogeyedpeas, you can't expect beating $n^2$ because it is the size of the input.

Note that if you are interested by the number of bit operations then you need to multiply this by the elementary cost of multiplication (for numbers of the size considered in your problem).

It you want to beat the $n^2$ bound, you need the $c_{a,b}$ to be represented in a more compact/structured way.

Answer 2

Assuming No Space Limitations:

To compute:

$$x^a \ \ mod \ \ n$$

Use modular exponentiation by squarings. Which takes roughly $O(ln(a))$

Be sure to store the values produced by the algorithm so that way later attempts to compute $x^a$ need not start from scratch and will be significantly faster than before (I have a feeling this is the type of detail you want heuristics on so I will try my best underneath)

The same process works for Y as well.

The total time becomes $O(n^2ln(n))$

Now for further detail:

If we 2D sort the elements $c_{a,b}$ based on the size of their coordinates we consume time:

$$O(nln(n)$$

At this point however if we begin to compute the values x^a and y^b we will be doing it step by incrementally and therefore the total computation time is:

$$nln(n)$$ but this being done at each step of the $n^2$ computations...

So the total time is:

$$O(n^2)$$

Cutting this down further I predict can be done via Quantum Computation.

sorry I believe I made a mistake:

The 2dimensional sort would take $n^2ln(n)$...

So the time complexity is:

$$O(n^2ln(n))$$

Sadly :(

Without bringing some kind of Quantum computation out the best you could ever do is $n^2$ as that's the time to just read the problem input. Manipulating it once it is read will likely be of similar complexity