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.

  • $\begingroup$ 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... $\endgroup$ – Joshua Grochow Dec 8 '18 at 3:24
  • $\begingroup$ 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)$. $\endgroup$ – 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:

enter image description here

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


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


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.