# Fast algorithms for evaluating functions with high Kolmogorov complexity

## 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:

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:

$$$$\text{Time}(F_k^N(n)) \sim \mathcal{O}(\ln n) \tag{1}$$$$

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$$:

$$$$\text{Time}(F_k^N(n)) \sim \ln K(F_k^N(n)) \tag{2}$$$$

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:

$$$$Q = \min_{f_i \in S} K(f_i) \tag{3}$$$$

and we may show that for almost all $$F_k^N$$ we must have:

$$$$K(F_k^N) \geq \frac{Q}{2} \cdot k^{N-1} \tag{4}$$$$

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:

$$$$n= Qk^{N -1} \tag{5}$$$$

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

$$$$\sum_{l=1}^{\frac{n}{2}} 2^l \leq 2^{\frac{n}{2}+1}-1 \tag{6}$$$$

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

$$$$\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}$$$$

## 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:

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

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
• 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 Jan 10 '20 at 22:05
• 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 Jan 10 '20 at 22:37
• (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 Jan 16 '20 at 16:20
• Reading your question made me think of this paper that you may have already encountered: arxiv.org/pdf/1801.10437.pdf – William de Vazelhes Apr 20 at 0:34
• 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 Apr 20 at 0:41