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

CC BY-SA 3.0
2016-09-20T15:23:50.110Z
I'm not sure if this was intentional, but the problem doesn't say we're given $y$, just $f(y)$.
Andrew Morgan
CC BY-SA 3.0
2016-09-21T09:13:01.430Z
@AndrewMorgan Depends on your application, for mine it's fine to assume y is given. Thank you for the comment!
Tatiana Starikovskaya
CC BY-SA 3.0
2016-09-21T16:56:41.867Z
@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
CC BY-SA 3.0
2016-09-20T12:17:38.667Z
2016-09-20T12:17:38.667Z
Joshua Grochow
<p>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.</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Parallel_Tree_Contraction" rel="noreferrer">rake-compress tree</a> 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.</p>

CC BY-SA 3.0
2016-09-22T00:43:54.167Z
2016-09-22T00:43:54.167Z
David Eppstein
<p>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$. </p>

<p>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?</p>

<p>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. </p>

<p>(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$.)</p>

<p>Is there anything better?</p>

<polynomials><dynamic-algorithms>
Maintaining the value of a polynomial over a dynamically updated input
Tatiana Starikovskaya
# Maintaining the value of a polynomial over a dynamically updated input

(Asked by: username_0 on 2016-09-19)

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?

**Tags:** polynomials, dynamic-algorithms


---

## 2 answers

### Answer by username_1 on 2016-09-20. Score: 7 | Accepted answer

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

> **Comments:**
> **username_2**: I'm not sure if this was intentional, but the problem doesn't say we're given $y$, just $f(y)$.  
> **username_0**: @AndrewMorgan Depends on your application, for mine it's fine to assume y is given. Thank you for the comment!  
> **username_1**: @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.)  

---

### Answer by username_3 on 2016-09-22. Score: 5

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](https://en.wikipedia.org/wiki/Parallel_Tree_Contraction) 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.


---

