<p>Not really an answer, but would've been too long a comment. The result of <a href="http://www.icsi.berkeley.edu/pubs/techreports/tr-90-13.pdf" rel="nofollow noreferrer">Ben-Or and Cleve</a> that arithmetic formulas can be simulated by branching programs of width 3, works over arbitrary non-commutative rings (in particular over the matrix ring $M_n(F)$). A nice consequence of this is that $\# NC^1$ circuits over $M_n(\mathbb{Z})$ captures ${\text{GapL}}$ over $\mathbb{Z}$ (for which the Determinant is a hard function). See for example, the <a href="http://iuuk.mff.cuni.cz/~koucky/papers/catalytic.pdf" rel="nofollow noreferrer">paper</a> on catalytic space by Buhrman et al. for an interesting generalization of the work of Ben-Or and Cleve. There is a result of <a href="https://arxiv.org/abs/1209.4865" rel="nofollow noreferrer">Capelli, Durand and Mengel</a> which gives a characterization of the arithmetic complexity class VP as equivalent to formulas whose nodes compute tensor contractions (note that here you even lose associativity). </p>

CC BY-SA 3.0
2017-06-10T14:30:44.067Z
Can you define "straight line program"? Also, lose the associativity of what? In the context of a computational model, getting rid of features of operators such as associativity is supposed to be a gain, not a loss.
einpoklum
CC BY-SA 3.0
2017-06-10T17:40:06.320Z
For tensors a, b, and c, $a*(b*c)$ is not necessarily the same as $(a*b)*c$. This makes evaluating them harder than say formulas operating over matrices. This probably also explains why arithmetic formulas over tensors capture VP whereas formulas over matrices only capture VBP (or GapL). There is some belief that VBP is strictly contained in VP. See https://arxiv.org/abs/1307.3863 for the definition of these classes.
Nikhil
CC BY-SA 3.0
2017-06-09T17:24:04.713Z
2017-06-10T17:09:13.923Z
2017-06-10T17:09:13.923Z
Nikhil
<p>Much ink has been spilled studying the theory surrounding computation by <a href="https://en.wikipedia.org/w/index.php?title=Combinatorial_circuit" rel="nofollow noreferrer">combinatorial circuits</a> operating on bits or boolean values - with AND, OR and NOT gates (as those are enough to implement any boolean function). One can consider families of these for different input sizes as opposed to general Turing machines, and consider the languages they accept or functions they compute (if they have multiple outputs); one can reason regarding their size and depth as a function of the input length; define the classes of languages acceptable by them with certain restrictions; study their composition; etc.</p>

<p>I've also been introduced to the <a href="https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine" rel="nofollow noreferrer">Blum-Shub-Smale</a> computational model, where the constituent operations of a program have elements of a field (e.g. the Rationals or the Reals) as inputs and outputs; and such a machine can be likened to a circuit if it has no loops or similar control structures. It's been the subject of much less theoretical literature, but I can still find tens of thousands of papers referring to the "BSS Model". And there are <a href="https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity" rel="nofollow noreferrer">arithmetic circuits</a> (with only + and * gates) which I vaguely recall from my Complexity Theory class as an undergrad (proofs about #P and PSPACE where boolean circuits get "arithmetized" -  AND into * and OR into +, with the inputs still being boolean).</p>

<p>But - what about circuits which operate on more complex units of data? That is, arrays of unbounded finite length - with the individual elements either all of some single type or from some vocabulary of types? Obviously, you might want to constrain the nodes in such circuits, as otherwise they would just be Turing machine or circuit families in themselves, but this is still a relevant kind of automaton to study these days - with programming models such as CUDA and OpenCL which apply these kinds of operations on very large amounts of data, controlled at the level of the entire kernels and their dependencies.</p>

<p>So - have circuits-operating-on-array seen any theoretical study? I've failed to find any such work so far.</p>

<p><strong>Note:</strong> RAM/register machines in which registers or individual memory cells contain arrays would be a next best thing.</p>

CC BY-SA 3.0
2017-06-06T08:03:06.460Z
I am not sure that this is what you are looking for but there has been some work on circuits operating on tensors [1,2]. Not really from the point of view of ML but you can still find some interesting results. [1] https://link.springer.com/article/10.1007/s00037-000-0170-4 ; [2] https://link.springer.com/article/10.1007/s00224-015-9630-8
holf
CC BY-SA 3.0
2017-06-07T06:34:13.260Z
It's not exactly what you are looking for, but [this paper](http://www.hpl.hp.com/techreports/Compaq-DEC/PRL-RR-25.pdf) by Jean Vuillemin deals, among other things, with circuits taking as inputs infinite streams of bits (he calls them *synchronous circuits*) and provides a characterization of what they may compute as functions on the ring of 2-adic integers (which are, indeed, infinite sequences of bits).
Damiano Mazza
CC BY-SA 3.0
2017-06-07T06:48:13.713Z
In another direction, perhaps more in the spirit of what you are looking for, I believe that linear/affine $\lambda$-terms may be seen as a higher-order generalization of Boolean circuits.  In particular, they may be seen as circuits taking as inputs essentially any traditional data structure (even circuits themselves, it's higher order).  Evidence of this is, among other things, a [higher-order version of the Cook-Levin theorem](https://www-lipn.univ-paris13.fr/~mazza/papers/ChurchCookLevin.pdf). I sincerely apologize for this self-promotion but I thought it'd be worthwhile mentioning.
Damiano Mazza
CC BY-SA 3.0
2017-06-07T08:39:34.707Z
@DamianoMazza: No apology is necessary, I'll check that out, although its quite the load of concepts to take in. Thanks.
einpoklum
CC BY-SA 3.0
2017-06-07T10:50:39.690Z
Yes, that paper is quite dense and does not really cover any of the aspects that may interest you. Unfortunately, I haven't written up anything more suitable; perhaps [this short abstract](https://lipn.univ-paris13.fr/~mazza/papers/HOBoolCirc.pdf) is better though.
Damiano Mazza
<automata-theory><circuit-complexity><arithmetic-circuits><circuits>
Has there been a study of circuits operating on arrays?
einpoklum
# Has there been a study of circuits operating on arrays?

(Asked by: username_0 on 2017-06-05)

Much ink has been spilled studying the theory surrounding computation by [combinatorial circuits](https://en.wikipedia.org/w/index.php?title=Combinatorial_circuit) operating on bits or boolean values - with AND, OR and NOT gates (as those are enough to implement any boolean function). One can consider families of these for different input sizes as opposed to general Turing machines, and consider the languages they accept or functions they compute (if they have multiple outputs); one can reason regarding their size and depth as a function of the input length; define the classes of languages acceptable by them with certain restrictions; study their composition; etc.

I've also been introduced to the [Blum-Shub-Smale](https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine) computational model, where the constituent operations of a program have elements of a field (e.g. the Rationals or the Reals) as inputs and outputs; and such a machine can be likened to a circuit if it has no loops or similar control structures. It's been the subject of much less theoretical literature, but I can still find tens of thousands of papers referring to the "BSS Model". And there are [arithmetic circuits](https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity) (with only + and \* gates) which I vaguely recall from my Complexity Theory class as an undergrad (proofs about #P and PSPACE where boolean circuits get "arithmetized" - AND into \* and OR into +, with the inputs still being boolean).

But - what about circuits which operate on more complex units of data? That is, arrays of unbounded finite length - with the individual elements either all of some single type or from some vocabulary of types? Obviously, you might want to constrain the nodes in such circuits, as otherwise they would just be Turing machine or circuit families in themselves, but this is still a relevant kind of automaton to study these days - with programming models such as CUDA and OpenCL which apply these kinds of operations on very large amounts of data, controlled at the level of the entire kernels and their dependencies.

So - have circuits-operating-on-array seen any theoretical study? I've failed to find any such work so far.

**Note:** RAM/register machines in which registers or individual memory cells contain arrays would be a next best thing.

**Tags:** automata-theory, circuit-complexity, arithmetic-circuits, circuits

> **Comments:**
> **username_1**: I am not sure that this is what you are looking for but there has been some work on circuits operating on tensors [1,2]. Not really from the point of view of ML but you can still find some interesting results. [1] https://link.springer.com/article/10.1007/s00037-000-0170-4 ; [2] https://link.springer.com/article/10.1007/s00224-015-9630-8  
> **username_2**: It's not exactly what you are looking for, but [this paper](http://www.hpl.hp.com/techreports/Compaq-DEC/PRL-RR-25.pdf) by Jean Vuillemin deals, among other things, with circuits taking as inputs infinite streams of bits (he calls them *synchronous circuits*) and provides a characterization of what they may compute as functions on the ring of 2-adic integers (which are, indeed, infinite sequences of bits).  
> **username_2**: In another direction, perhaps more in the spirit of what you are looking for, I believe that linear/affine $\lambda$-terms may be seen as a higher-order generalization of Boolean circuits.  In particular, they may be seen as circuits taking as inputs essentially any traditional data structure (even circuits themselves, it's higher order).  Evidence of this is, among other things, a [higher-order version of the Cook-Levin theorem](https://www-lipn.univ-paris13.fr/~mazza/papers/ChurchCookLevin.pdf). I sincerely apologize for this self-promotion but I thought it'd be worthwhile mentioning.  
> **username_0**: @DamianoMazza: No apology is necessary, I'll check that out, although its quite the load of concepts to take in. Thanks.  
> **username_2**: Yes, that paper is quite dense and does not really cover any of the aspects that may interest you. Unfortunately, I haven't written up anything more suitable; perhaps [this short abstract](https://lipn.univ-paris13.fr/~mazza/papers/HOBoolCirc.pdf) is better though.  

---

## 1 answers

### Answer by username_3 on 2017-06-09. Score: 2

Not really an answer, but would've been too long a comment. The result of [Ben-Or and Cleve](http://www.icsi.berkeley.edu/pubs/techreports/tr-90-13.pdf) that arithmetic formulas can be simulated by branching programs of width 3, works over arbitrary non-commutative rings (in particular over the matrix ring $M\_n(F)$). A nice consequence of this is that $\# NC^1$ circuits over $M\_n(\mathbb{Z})$ captures ${\text{GapL}}$ over $\mathbb{Z}$ (for which the Determinant is a hard function). See for example, the [paper](http://iuuk.mff.cuni.cz/~koucky/papers/catalytic.pdf) on catalytic space by Buhrman et al. for an interesting generalization of the work of Ben-Or and Cleve. There is a result of [Capelli, Durand and Mengel](https://arxiv.org/abs/1209.4865) which gives a characterization of the arithmetic complexity class VP as equivalent to formulas whose nodes compute tensor contractions (note that here you even lose associativity).

> **Comments:**
> **username_0**: Can you define "straight line program"? Also, lose the associativity of what? In the context of a computational model, getting rid of features of operators such as associativity is supposed to be a gain, not a loss.  
> **username_3**: For tensors a, b, and c, $a*(b*c)$ is not necessarily the same as $(a*b)*c$. This makes evaluating them harder than say formulas operating over matrices. This probably also explains why arithmetic formulas over tensors capture VP whereas formulas over matrices only capture VBP (or GapL). There is some belief that VBP is strictly contained in VP. See https://arxiv.org/abs/1307.3863 for the definition of these classes.  

---

