A key feature of neural network architectures is their ability to support simultaneous interactions among a large number of units in the learning and processing of representations. However, how the richness of such interactions trades off against the ability of a network to simultaneously carry out multiple independent processes remains largely unexplored.

In this work we use a graph-theoretic analysis of network architecture to address this question for tasks that are represented as edges in a bipartite graph. We define a new measure of multitasking capacity of such networks, based on the model where tasks that need to be multitasked rely on independent resources, i.e., form a matching in the graph, and that tasks can be multitasked without interference if they form an induced matching in the graph.

We demonstrate networks that posses the desirable multitasking properties. We also show inherent limitations on the trade-off between the multitasking capacity and the average degree of the network. Our results shed light into the parallel-processing limitations of neural systems, and provide insights that may be useful for the analysis and design of parallel architectures.