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).