5
$\begingroup$

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.

$\endgroup$
  • $\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
1
$\begingroup$

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:

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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