patternMinor
What is the relation between arithmetic circuits and straight line programs?
Viewed 0 times
thewhatlinebetweencircuitsstraightprogramsandrelationarithmetic
Problem
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.)
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.)
Solution
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:
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).
- Reading the input: $t_i \gets x_j$.
- Initialization by constants: $t_i \gets r$ for all $r$ in the ambient field.
- Addition, subtraction, multiplication, division: $t_t \gets t_j \pm t_k$ and so on.
- 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).
Context
StackExchange Computer Science Q#35890, answer score: 5
Revisions (0)
No revisions yet.