Evaluation of an arithmetic formula where the time depends on the length of the arguments of gates

Question

Let $(X,+,\cdot)$ be a commutative ring. Let $|\cdot|\colon X\to \mathbb{N}$ be a function that satisfies $|x+y|\leq |x|+|y|$ and $|xy|\leq |x|+|y|$. We call the function length, and length is always positive. We are given an arithmetic formula(arithmetic circuit with outdegree 1) of size $n$, over $X$ with gates $+$ and $\cdot$. There are no constant terms.

The time to evaluate a gate with input $x$ and $y$ is $O(|x|+|y|)$.

Is it possible to evaluate the formula in $O(m\log n)$ time? where $m$ is the total length of the input.

Answer 1

EDIT: I was wrong about the implication to arithmetic circuits.

I think it is possible. It uses ideas in parallel evaluation of arithmetic expressions and tree contraction.

Consider the arithmetic formula, it is an arithmetic circuit that forms a directed tree. Consider each gate as a function of the form $f(x,y) = a(x\square y)+b$ for constant $a,b$ and operation $\square$. So, a $\square$ gate is $1(x\square y)+0$. We call $a$ the linear part, and $b$ the constant part. One can evaluate the formula by a "tree contraction" operation. It takes 3 vertices $u,v,w$ and returns one new vertex in this tree. Here $u,v$ are children of $w$, and $u$ is a leaf. That is, we can delete node $u$, contract $w$ and $v$ into to a new vertex $w'$, and the gate for $w'$ is a function of the form $a(x\square y)+b$ for some constants $a$ and $b$, and we have the tree evaluates to the same value.

Here is an example:

Let $\ell(v)$ be the labels of $v$, defined as all the input used to compute the linear and constant part of the gate $v$.

Facts:

1. One can apply tree contraction to a constant fraction of vertices in parallel. Let such parallel operation be called a single iteration.

2. At any moment of the computation, $\{\ell(v) | v\in V_t\}$ forms a partition of the input, where $V_t$ is the vertices of the formula after the $t$th contraction.

3. The coefficient of the linear term and constant term on each node can be expressed as a single-use expression (i.e. each variable in the input is used at most once). It implies if $y$ is the constant part or linear part of the vertex $v$, then $|y| \leq \sum_{x\in \ell(v)} |x|$. Note this fact is only used to bound the size of the coefficient. The computation of the coefficient itself is not related to the single-use expression.

Consider an algorithm that does $O(\log(n))$ iterations of tree contraction in parallel, and get a constant size tree. We evaluate the final tree directly. In each iteration, the running time is bounded by the sum of the size of the labels for each node, which is $O(m)$ due to disjointness of the label sets over the vertices.

Together the running time is $O(m\log n)=O(m\log n)$.