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

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.

• Is the description of the circuit part of the input? Or did you mean $O(n \log m)$? I find it hard to imagine one can evaluate $n$ gates in much less than $\Omega(n)$ time, and probably for many rings a counting-type argument will prove a statement of this flavor... – Joshua Grochow Dec 8 '18 at 3:24
• The formula is part of the input. I added that the length is positive, and there are no constant terms, which shows m=$\Omega(n)$. – Chao Xu Dec 8 '18 at 7:52

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