10
$\begingroup$

Let $P(x_1, x_2, \ldots, x_n)$ be a polynomial over a fixed finite field. Suppose we are given the value of $P$ on some vector $y \in \{0,1\}^n$ and the vector $y$.

We now want to compute the value of $P$ on a vector $y' \in \{0,1\}^n$ such that $y$ and $y'$ differ on exactly one position (in other words, we flip exactly one bit in $y$). What are the space and the time trade-offs for this problem?

For example, if $r$ is the number of monomials in $P$, we can store the coefficients and the values of all monomials in $P$. If $y_i$ is flipped, we fix the value of each monomial containing $y_i$ and then the value of $P(y)$ using the stored information. Overall, we need $O(r)$ time and space.

(I do not say anything about how we identify the monomials containing $y_i$ for purpose. You can choose any reasonable representation of $P$, in the example I assume that we store a list of monomials containing $y_i$ for each $i$.)

Is there anything better?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

Your idea generalizes as follows: given an algebraic circuit (over the finite field) or Boolean circuit (computing the bit-wise representation of your finite field elements) computing $P$, then maintain the value at each gate in the circuit. When you change the $i$-th bit of $y$, simply propagate that change along the DAG of the circuit, starting from the input $y_i$. If the circuit has size $s$, this takes $O(s)$ time and space. This could be much smaller than the number of monomials (which corresponds to the size of algebraic circuits of depth only 2).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I'm not sure if this was intentional, but the problem doesn't say we're given $y$, just $f(y)$. $\endgroup$
    – Andrew Morgan
    Commented Sep 20, 2016 at 15:23
  • 1
    $\begingroup$ @AndrewMorgan Depends on your application, for mine it's fine to assume y is given. Thank you for the comment! $\endgroup$
    – Tatiana Starikovskaya
    Commented Sep 21, 2016 at 9:13
  • 2
    $\begingroup$ @AndrewMorgan: Indeed, while this is technically true, the way the example construction in the OQ was phrased seemed to implicitly assume that $y$ is given. If $y$ is not given, I think this problem becomes much harder. (Tatiana, it may be worth adding this as a clarification to the question.) $\endgroup$
    – Joshua Grochow
    Commented Sep 21, 2016 at 16:56
5
$\begingroup$

It's easy to modify your monomial-storing approach so that each update takes time only proportional to the number of changed monomials: just update the total polynomial value by adding the new value and subtracting the old value for each changed monomial.

If you have a read-once formula for $P$ (i.e. every variable appears at a single leaf of the formula tree, and each internal node is a two-input arithmetic operation like plus or times) then you can maintain the value of $P$ in logarithmic time per update using a rake-compress tree over the formula. Applying this approach to an arbitrary formula, the time to update a variable that appears $k$ times will be $O(k\log N)$ where $N$ is the formula size. So except for the log factor this generalizes the bound for the number of changed monomials, and applies to more general types of expansion of the polynomial into a formula.

Improve this answer
$\endgroup$

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.