# Maintaining the value of a polynomial over a dynamically updated input

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?

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).
• I'm not sure if this was intentional, but the problem doesn't say we're given $y$, just $f(y)$. – Andrew Morgan Sep 20 '16 at 15:23
• @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.) – Joshua Grochow Sep 21 '16 at 16:56
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.