4
$\begingroup$

One definition of arithmetic circuits is as follows:

An arithmetic circuit $\Phi$ over the field $\mathbb F$ and the set of variables $X$ usually, $X = \{x_1, \dots , x_n\}$) is a directed acyclic graph as follows. The vertices of $\Phi$ are called gates. Every gate in $\Phi$ of in-degree $0$ is labeled by either a variable from $X$ or a field element from $\mathbb F$. Every other gate in $\Phi$ is labeled by either $\times$ or $+$ and has in-degree $2$.

A straight-line program seems to be a succession of basic operations without any if or while statement. So it seems to be a term from the associated free algebra expressed suitably "compressed" as an acyclic graph. But a (reference to a) nice definition of straight-line programs would already help me a bit with respect to this question.

What I really want to know is whether an arithmetic circuit is a special case of a straight-line program? If yes, then why is arithmetic circuit complexity considered so important, while even finding a reference for a proper definition of straight-line programs seems to be quite challenging? (I found a definition in The Extraordinary Power of Division in Straight Line Programs, but this is a paper from 2012, and the notion itself seems to be much older.)

$\endgroup$
  • 1
    $\begingroup$ +1 for reference to the Borwein Hobart paper. Not sure if it helps but Lipton posted a write up on his blog regarding that paper. $\endgroup$ – J C Jan 4 '15 at 20:15
6
$\begingroup$

Straight-line programs and arithmetic circuits are two equivalent ways of describing the same computational model. A straight-line program typically has the following instructions:

  1. Reading the input: $t_i \gets x_j$.
  2. Initialization by constants: $t_i \gets r$ for all $r$ in the ambient field.
  3. Addition, subtraction, multiplication, division: $t_t \gets t_j \pm t_k$ and so on.
  4. Output: $o_i \gets t_j$.

The input and output instructions aren't really necessary. The inputs are $x_1,\ldots,x_n$ and the outputs are $o_1,\ldots,o_m$.

Exercise: show that (multiple-output) arithmetic circuits and straight-line programs are equivalent: they compute the same functions with the same size complexity (if you define size in the correct way, and allow the same sets of gates and lines).

$\endgroup$
  • $\begingroup$ Is a straight line program natural way to 'computationally categorize' rings? $\endgroup$ – T.... Jan 5 '15 at 10:39
  • $\begingroup$ Perhaps, though I'm not sure what computationally categorize means. $\endgroup$ – Yuval Filmus Jan 5 '15 at 11:42

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.