# A spiking neural algorithm for the Network Flow problem

arXiv: https://arxiv.org/abs/1911.13097 · HTML: https://mlsanity.com/paper/1911.13097/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2019.

## Built on by (most cited first, 2 of 2)

- [SpikE: spike-based embeddings for multi-relational graph data](https://mlsanity.com/paper/2104.13398/) (2021)
- [Neuro-symbolic computing with spiking neural networks](https://mlsanity.com/paper/2208.02576/) (2022)

## Abstract (arXiv)

It is currently not clear what the potential is of neuromorphic hardware beyond machine learning and neuroscience. In this project, a problem is investigated that is inherently difficult to fully implement in neuromorphic hardware by introducing a new machine model in which a conventional Turing machine and neuromorphic oracle work together to solve such types of problems. We show that the P-complete Max Network Flow problem is intractable in models where the oracle may be consulted only once (`create-and-run' model) but becomes tractable using an interactive (`neuromorphic co-processor') model of computation. More in specific we show that a logspace-constrained Turing machine with access to an interactive neuromorphic oracle with linear space, time, and energy constraints can solve Max Network Flow. A modified variant of this algorithm is implemented on the Intel Loihi chip; a neuromorphic manycore processor developed by Intel Labs. We show that by off-loading the search for augmenting paths to the neuromorphic processor we can get energy efficiency gains, while not sacrificing runtime resources. This result demonstrates how P-complete problems can be mapped on neuromorphic architectures in a theoretically and potentially practically efficient manner.