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

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. Each linear part and constant part can be expressed as an expression where each variable in the input is used at most once.

Consider an algorithm that does $O(\log(n))$ iterations of tree contraction in parallel, and get a constant size circuit. We evaluate the final circuit by brute force. One can simulate this algorithm with a single arithmetic circuit.

Theorem: For an arithmetic formula of $n$ nodes, there exists an arithmetic circuit of depth $O(\log n)$, size $O(n)$, each input reaches $O(\log n)$ vertices, and the underlying graph with the final gate removed is a tree.

Intuitively, the underlying graph with the final gate removed is a tree implies each input "participates" in each gate at most once. Each input participates in at most $O(\log n)$ gates. Together the running time is $O(\sum_{x} s(x) \log n )=O(m\log n)$.