<h2>Motivation:</h2>
<p>I am motivated by a concrete example that occurs in neuroscience, dendritic computation, which may be approximated by functions computable on binary trees [1]. To be more precise, I recently realised that a large class of functions computable on <span class="math-container">$k$</span>-ary trees have both logarithmic time-complexity for inference(i.e. function evaluation) and Kolmogorov Complexity that grows exponentially with tree depth.</p>
<p>This motivates the study of algorithms for inference that are both very fast <span class="math-container">$\mathcal{O}(\ln n)$</span> and whose models(in this case functions) are very expressive in the sense of algorithmic information. For concreteness I shall start by sharing my analysis of functions computable on <span class="math-container">$k$</span>-ary trees .</p>
<h2> Functions computable on <span class="math-container">$k$</span>-ary trees:</h2>
<p>Let's define a function <span class="math-container">$F_k^N$</span> computable on a <span class="math-container">$k$</span>-ary tree with depth <span class="math-container">$N$</span> as a function composed with <span class="math-container">$\sum_{n=0}^{N-1} k^n = \frac{k^N-1}{k-1}$</span> simpler computable functions(ex. boolean gates, neural network activation functions composed with affine transformations) defined at each node such that a function of this kind defined on a binary tree of depth <span class="math-container">$N$</span> receives <span class="math-container">$2^{N-1}$</span> inputs:</p>
<p><a href="https://i.sstatic.net/mQ5Ka.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/mQ5Ka.png" alt="enter image description here" /></a></p>
<p>In general, the input to <span class="math-container">$k$</span>-ary trees grows on the order of <span class="math-container">$k^N$</span>. On the other hand, if the computational cost of function execution at each node is bounded by a constant <span class="math-container">$C$</span> then parallel execution of <span class="math-container">$F_k^N$</span> yields an asymptotic time complexity proportional to tree depth <span class="math-container">$N$</span> so we have:</p>
<p><span class="math-container">\begin{equation}
\text{Time}(F_k^N(n)) \sim \mathcal{O}(\ln n) \tag{1}
\end{equation}</span></p>
<p>Meanwhile, if <span class="math-container">$F_k^N$</span> is a composition of functions in <span class="math-container">$S$</span> where <span class="math-container">$\lvert S \rvert = \frac{k^{N}-1}{k-1}$</span> and <span class="math-container">$K(\cdot)$</span> denotes Kolmogorov Complexity we can also show that for almost all <span class="math-container">$F_k^N$</span>:</p>
<p><span class="math-container">\begin{equation}
\text{Time}(F_k^N(n)) \sim \ln K(F_k^N(n)) \tag{2}
\end{equation}</span></p>
<p>which means that the Kolmogorov Complexity of <span class="math-container">$F_k^N$</span> is an exponential function of the time complexity of <span class="math-container">$F_k^N$</span>.</p>
<h2> Probabilistic analysis using Kolmogorov Complexity:</h2>
<p>If <span class="math-container">$F_k^N$</span> is a composition of functions in <span class="math-container">$S$</span> where <span class="math-container">$\lvert S \rvert = \frac{k^{N}-1}{k-1}$</span> and <span class="math-container">$K(\cdot)$</span> denotes Kolmogorov Complexity then we may define:</p>
<p><span class="math-container">\begin{equation}
Q = \min_{f_i \in S} K(f_i) \tag{3}
\end{equation}</span></p>
<p>and we may show that for almost all <span class="math-container">$F_k^N$</span> we must have:</p>
<p><span class="math-container">\begin{equation}
K(F_k^N) \geq \frac{Q}{2} \cdot k^{N-1} \tag{4}
\end{equation}</span></p>
<p><strong>Proof:</strong></p>
<p>Let's suppose each <span class="math-container">$f_i \in S$</span> has an encoding as a binary string so <span class="math-container">$\forall i, f_i \in \{0,1\}^*$</span>. If we compress each <span class="math-container">$f_i$</span> then <span class="math-container">$F_k^N$</span> is reduced to a program of length greater than:</p>
<p><span class="math-container">\begin{equation}
n= Qk^{N -1} \tag{5}
\end{equation}</span></p>
<p>Now, the number of programs of length less than or equal to <span class="math-container">$\frac{n}{2}$</span> is given by:</p>
<p><span class="math-container">\begin{equation}
\sum_{l=1}^{\frac{n}{2}} 2^l \leq 2^{\frac{n}{2}+1}-1 \tag{6}
\end{equation}</span></p>
<p>and so, using the principle of maximum entropy(i.e. uniform distribution) [3], we find that:</p>
<p><span class="math-container">\begin{equation}
\lim_{n \to \infty} P(K(F_k^N) \geq \frac{n}{2}) \geq \lim_{n \to \infty} 1 - \frac{2^{\frac{n}{2}}}{2^n} = 1 \tag{7}
\end{equation}</span></p>
<h2>Question:</h2>
<p>Might there be a branch of theoretical computer science devoted to the study of functions <span class="math-container">$F$</span> that accept high-dimensional inputs and almost surely satisfy:</p>
<p><span class="math-container">\begin{equation}
F = \{P:  \text{Time}(P(n)) \sim \mathcal{O}(\ln n) \land \text{Time}(P(n)) \lesssim  \ln K(P(n)) \} \tag{8}
\end{equation}</span></p>
<p>I am curious about the properties of the associated algorithms for fast function evaluation. Are all these algorithms massively parallel? Do they necessarily exploit symmetries on multiple scales?</p>
<p>My hunch is that algorithms which satisfy these properties are of great importance in theoretical biology.</p>
<p><strong>Note:</strong> In case it is not clear, in the example I gave I am assuming parallel execution of functions at each level of <span class="math-container">$F_k^N$</span>.</p>
<h2>References:</h2>
<ol>
<li>Roozbeh Farhoodi, Khashayar Filom, Ilenna Simone Jones, Konrad Paul Kording. On functions computed on trees. Arxiv. 2019.</li>
<li>M. Li and P. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Graduate Texts in Computer Science. Springer, New York, second edition, 1997.</li>
<li>Edwin Jaynes. Information Theory and Statistical Mechanics. The Physical Review. Vol. 106. No 4. 620-630. May 15, 1957.</li>
<li>Michael London &amp; Michael Häusser. Dendritic Computation. Annu. Rev. Neurosci. 2005. 28:503–32</li>
</ol>

CC BY-SA 4.0
2020-01-10T22:05:52.303Z
I think the question should be made much more precise before any attempt to answer it. What is the computational model? Now it looks like "tree has depth logarithmic compared to its size", which is certainly true...
user40487
CC BY-SA 4.0
2020-01-10T22:37:53.857Z
I am assuming parallel execution at each level, a form of concurrent processing. I also state this before introducing the first equation. Perhaps I should have stated this a bit more clearly? 

Or perhaps you mean something else by computational model?
Aidan Rocke
CC BY-SA 4.0
2020-01-16T15:00:27.877Z
The post says "*for almost all $F_k^N$*".  But the post doesn't say what operators  the individual gates can have,  Do you intend logical and, logical or, nand, xor, ...?  I suggest editing the post to specify -- otherwise I think the class of functions in question is not well defined.
Neal Young
CC BY-SA 4.0
2020-01-16T15:21:41.083Z
@NealYoung Thank you for pointing this out. I was thinking of both boolean gates and neural network activation functions composed with affine transformations.
Aidan Rocke
CC BY-SA 4.0
2020-01-16T16:20:51.450Z
(i) What do you mean by the K-complexity of a function?  K-complexity is defined w.r.t. strings. The proof given seems to assume that the K-complexity of $F_k^N$ is the K-complexity of its obvious encoding.  A more natural notion might be the size of the smallest TM that computes it.  With this definition the proof has a gap, because there might be a TM smaller than obvious one. (ii) For a fixed n, consider the class of functions $f_s$ such that $f_s(x) = 1$ iff $x=s$; where $s$ ranges over n-bit strings. This class has the properties you seem to be focusing on, but is arguably uninteresting.
Neal Young
CC BY-SA 4.0
2021-04-20T00:34:37.217Z
Reading your question made me think of this paper that you may have already encountered: https://arxiv.org/pdf/1801.10437.pdf
William de Vazelhes
CC BY-SA 4.0
2021-04-20T00:41:48.890Z
In this paper, they analyze the logical depth of DNNs, which may be related to the time vs Kolmogorov complexity tradeoff that you mention (it’s the time of execution of the shortest program to produce a string)
William de Vazelhes
<reference-request><time-complexity><dc.parallel-comp><kolmogorov-complexity>
Fast algorithms for evaluating functions with high Kolmogorov complexity
Aidan Rocke
# Fast algorithms for evaluating functions with high Kolmogorov complexity

(Asked by: username_0 on 2020-01-09)

## Motivation:

I am motivated by a concrete example that occurs in neuroscience, dendritic computation, which may be approximated by functions computable on binary trees [1]. To be more precise, I recently realised that a large class of functions computable on $k$-ary trees have both logarithmic time-complexity for inference(i.e. function evaluation) and Kolmogorov Complexity that grows exponentially with tree depth.

This motivates the study of algorithms for inference that are both very fast $\mathcal{O}(\ln n)$ and whose models(in this case functions) are very expressive in the sense of algorithmic information. For concreteness I shall start by sharing my analysis of functions computable on $k$-ary trees .

## Functions computable on $k$-ary trees:

Let's define a function $F\_k^N$ computable on a $k$-ary tree with depth $N$ as a function composed with $\sum\_{n=0}^{N-1} k^n = \frac{k^N-1}{k-1}$ simpler computable functions(ex. boolean gates, neural network activation functions composed with affine transformations) defined at each node such that a function of this kind defined on a binary tree of depth $N$ receives $2^{N-1}$ inputs:

[![enter image description here](https://i.sstatic.net/mQ5Ka.png)](https://i.sstatic.net/mQ5Ka.png)

In general, the input to $k$-ary trees grows on the order of $k^N$. On the other hand, if the computational cost of function execution at each node is bounded by a constant $C$ then parallel execution of $F\_k^N$ yields an asymptotic time complexity proportional to tree depth $N$ so we have:

\begin{equation}
\text{Time}(F\_k^N(n)) \sim \mathcal{O}(\ln n) \tag{1}
\end{equation}

Meanwhile, if $F\_k^N$ is a composition of functions in $S$ where $\lvert S \rvert = \frac{k^{N}-1}{k-1}$ and $K(\cdot)$ denotes Kolmogorov Complexity we can also show that for almost all $F\_k^N$:

\begin{equation}
\text{Time}(F\_k^N(n)) \sim \ln K(F\_k^N(n)) \tag{2}
\end{equation}

which means that the Kolmogorov Complexity of $F\_k^N$ is an exponential function of the time complexity of $F\_k^N$.

## Probabilistic analysis using Kolmogorov Complexity:

If $F\_k^N$ is a composition of functions in $S$ where $\lvert S \rvert = \frac{k^{N}-1}{k-1}$ and $K(\cdot)$ denotes Kolmogorov Complexity then we may define:

\begin{equation}
Q = \min\_{f\_i \in S} K(f\_i) \tag{3}
\end{equation}

and we may show that for almost all $F\_k^N$ we must have:

\begin{equation}
K(F\_k^N) \geq \frac{Q}{2} \cdot k^{N-1} \tag{4}
\end{equation}

**Proof:**

Let's suppose each $f\_i \in S$ has an encoding as a binary string so $\forall i, f\_i \in \{0,1\}^\*$. If we compress each $f\_i$ then $F\_k^N$ is reduced to a program of length greater than:

\begin{equation}
n= Qk^{N -1} \tag{5}
\end{equation}

Now, the number of programs of length less than or equal to $\frac{n}{2}$ is given by:

\begin{equation}
\sum\_{l=1}^{\frac{n}{2}} 2^l \leq 2^{\frac{n}{2}+1}-1 \tag{6}
\end{equation}

and so, using the principle of maximum entropy(i.e. uniform distribution) [3], we find that:

\begin{equation}
\lim\_{n \to \infty} P(K(F\_k^N) \geq \frac{n}{2}) \geq \lim\_{n \to \infty} 1 - \frac{2^{\frac{n}{2}}}{2^n} = 1 \tag{7}
\end{equation}

## Question:

Might there be a branch of theoretical computer science devoted to the study of functions $F$ that accept high-dimensional inputs and almost surely satisfy:

\begin{equation}
F = \{P: \text{Time}(P(n)) \sim \mathcal{O}(\ln n) \land \text{Time}(P(n)) \lesssim \ln K(P(n)) \} \tag{8}
\end{equation}

I am curious about the properties of the associated algorithms for fast function evaluation. Are all these algorithms massively parallel? Do they necessarily exploit symmetries on multiple scales?

My hunch is that algorithms which satisfy these properties are of great importance in theoretical biology.

**Note:** In case it is not clear, in the example I gave I am assuming parallel execution of functions at each level of $F\_k^N$.

## References:

1. Roozbeh Farhoodi, Khashayar Filom, Ilenna Simone Jones, Konrad Paul Kording. On functions computed on trees. Arxiv. 2019.
2. M. Li and P. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Graduate Texts in Computer Science. Springer, New York, second edition, 1997.
3. Edwin Jaynes. Information Theory and Statistical Mechanics. The Physical Review. Vol. 106. No 4. 620-630. May 15, 1957.
4. Michael London & Michael Häusser. Dendritic Computation. Annu. Rev. Neurosci. 2005. 28:503–32

**Tags:** reference-request, time-complexity, dc.parallel-comp, kolmogorov-complexity

> **Comments:**
> **username_1**: I think the question should be made much more precise before any attempt to answer it. What is the computational model? Now it looks like "tree has depth logarithmic compared to its size", which is certainly true...  
> **username_0**: I am assuming parallel execution at each level, a form of concurrent processing. I also state this before introducing the first equation. Perhaps I should have stated this a bit more clearly?   Or perhaps you mean something else by computational model?  
> **username_2**: The post says "*for almost all $F_k^N$*".  But the post doesn't say what operators  the individual gates can have,  Do you intend logical and, logical or, nand, xor, ...?  I suggest editing the post to specify -- otherwise I think the class of functions in question is not well defined.  
> **username_0**: @NealYoung Thank you for pointing this out. I was thinking of both boolean gates and neural network activation functions composed with affine transformations.  
> **username_2**: (i) What do you mean by the K-complexity of a function?  K-complexity is defined w.r.t. strings. The proof given seems to assume that the K-complexity of $F_k^N$ is the K-complexity of its obvious encoding.  A more natural notion might be the size of the smallest TM that computes it.  With this definition the proof has a gap, because there might be a TM smaller than obvious one. (ii) For a fixed n, consider the class of functions $f_s$ such that $f_s(x) = 1$ iff $x=s$; where $s$ ranges over n-bit strings. This class has the properties you seem to be focusing on, but is arguably uninteresting.  
> **username_3**: Reading your question made me think of this paper that you may have already encountered: https://arxiv.org/pdf/1801.10437.pdf  
> **username_3**: In this paper, they analyze the logical depth of DNNs, which may be related to the time vs Kolmogorov complexity tradeoff that you mention (it’s the time of execution of the shortest program to produce a string)  

---

## 0 answers

