6
$\begingroup$

Much ink has been spilled studying the theory surrounding computation by combinatorial circuits 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 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 (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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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] link.springer.com/article/10.1007/s00037-000-0170-4 ; [2] link.springer.com/article/10.1007/s00224-015-9630-8 $\endgroup$
    – holf
    Jun 6, 2017 at 8:03
  • 1
    $\begingroup$ It's not exactly what you are looking for, but this paper 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). $\endgroup$
    – Damiano Mazza
    Jun 7, 2017 at 6:34
  • $\begingroup$ 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. I sincerely apologize for this self-promotion but I thought it'd be worthwhile mentioning. $\endgroup$
    – Damiano Mazza
    Jun 7, 2017 at 6:48
  • $\begingroup$ @DamianoMazza: No apology is necessary, I'll check that out, although its quite the load of concepts to take in. Thanks. $\endgroup$
    – einpoklum
    Jun 7, 2017 at 8:39
  • $\begingroup$ 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 is better though. $\endgroup$
    – Damiano Mazza
    Jun 7, 2017 at 10:50

1 Answer 1

Reset to default
2
$\begingroup$

Not really an answer, but would've been too long a comment. The result of Ben-Or and Cleve 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 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 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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – einpoklum
    Jun 10, 2017 at 14:30
  • $\begingroup$ 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 arxiv.org/abs/1307.3863 for the definition of these classes. $\endgroup$
    – Nikhil
    Jun 10, 2017 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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