<p><strong>EDIT:</strong> I was wrong about the implication to arithmetic circuits.</p>

<p>I think it is possible. It uses ideas in <a href="https://dl.acm.org/citation.cfm?id=321815" rel="nofollow noreferrer">parallel evaluation of arithmetic expressions</a> and <a href="https://www.sciencedirect.com/science/article/pii/0196677489900175" rel="nofollow noreferrer">tree contraction</a>. </p>

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

<p>Here is an example:</p>

<p><a href="https://i.sstatic.net/nGSnT.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/nGSnT.png" alt="enter image description here"></a></p>

<p>Let <span class="math-container">$\ell(v)$</span> be the labels of <span class="math-container">$v$</span>, defined as all the input used to compute the linear and constant part of the gate <span class="math-container">$v$</span>.</p>

<p>Facts:</p>

<ol>
<li><p>One can apply tree contraction to a constant fraction of vertices <strong>in 
parallel</strong>. Let such parallel operation be called a single iteration.</p></li>
<li><p>At any moment of the computation, <span class="math-container">$\{\ell(v) | v\in V_t\}$</span> forms a partition of the input, where <span class="math-container">$V_t$</span> is the vertices of the formula after the <span class="math-container">$t$</span>th contraction.</p></li>
<li><p>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 <span class="math-container">$y$</span> is the constant part or linear part of the vertex <span class="math-container">$v$</span>, then <span class="math-container">$|y| \leq \sum_{x\in \ell(v)} |x|$</span>. 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.</p></li>
</ol>

<p>Consider an algorithm that does <span class="math-container">$O(\log(n))$</span> 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 <span class="math-container">$O(m)$</span> due to disjointness of the label sets over the vertices.</p>

<p>Together the running time is <span class="math-container">$O(m\log n)=O(m\log n)$</span>.</p>

CC BY-SA 4.0
2018-12-17T00:46:54.053Z
2019-02-18T17:25:10.210Z
2019-02-18T17:25:10.210Z
Chao Xu
<p>Let <span class="math-container">$(X,+,\cdot)$</span> be a commutative ring. Let <span class="math-container">$|\cdot|\colon X\to \mathbb{N}$</span> be a function that satisfies <span class="math-container">$|x+y|\leq |x|+|y|$</span> and <span class="math-container">$|xy|\leq |x|+|y|$</span>. We call the function length, and length is always positive. 
We are given an arithmetic formula(arithmetic circuit with outdegree 1) of size <span class="math-container">$n$</span>, over <span class="math-container">$X$</span> with gates <span class="math-container">$+$</span> and <span class="math-container">$\cdot$</span>. There are no constant terms.</p>

<p>The time to evaluate a gate with input <span class="math-container">$x$</span> and <span class="math-container">$y$</span> is <span class="math-container">$O(|x|+|y|)$</span>.</p>

<p>Is it possible to evaluate the formula in <span class="math-container">$O(m\log n)$</span> time? where <span class="math-container">$m$</span> is the total length of the input. </p>

CC BY-SA 4.0
2018-12-08T03:24:01.770Z
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
CC BY-SA 4.0
2018-12-08T07:52:20.140Z
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
<ds.algorithms><arithmetic-circuits>
Evaluation of an arithmetic formula where the time depends on the length of the arguments of gates
Chao Xu
# Evaluation of an arithmetic formula where the time depends on the length of the arguments of gates

(Asked by: username_0 on 2018-12-08)

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.

**Tags:** ds.algorithms, arithmetic-circuits

> **Comments:**
> **username_1**: 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...  
> **username_0**: 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)$.  

---

## 1 answers

### Answer by username_0 on 2018-12-17. Score: 1 | Accepted answer

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

I think it is possible. It uses ideas in [parallel evaluation of arithmetic expressions](https://dl.acm.org/citation.cfm?id=321815) and [tree contraction](https://www.sciencedirect.com/science/article/pii/0196677489900175).

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](https://i.sstatic.net/nGSnT.png)](https://i.sstatic.net/nGSnT.png)

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


---

