Skip to main content

A graph-theoretic approach to multitasking

Author(s): Alon, Noga; Reichman, Daniel; Shinkar, Igor; Wagner, Tal; Musslick, Sebastian; et al

To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorAlon, Noga-
dc.contributor.authorReichman, Daniel-
dc.contributor.authorShinkar, Igor-
dc.contributor.authorWagner, Tal-
dc.contributor.authorMusslick, Sebastian-
dc.contributor.authorCohen, Jonathan D.-
dc.contributor.authorGriffiths, Thomas L.-
dc.contributor.authorDey, Biswadip-
dc.contributor.authorOzcimder, Kayhan-
dc.identifier.citationAlon, N, Reichman, D, Shinkar, I, Wagner, T, Musslick, S, Cohen, JD, Griffiths, TL, Dey, B, Ozcimder, K. (2017). A graph-theoretic approach to multitasking. Advances in Neural Information Processing Systems, 2017-December (2101 - 2110)en_US
dc.description.abstract© 2017 Neural information processing systems foundation. All rights reserved. A key feature of neural network architectures is their ability to support the simultaneous interaction among large numbers 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 - a salient limitation in many domains of human cognition - remains largely unexplored. In this paper we use a graph-theoretic analysis of network architecture to address this question, where tasks are represented as edges in a bipartite graph G = (A ⊃ B,E). We define a new measure of multitasking capacity of such networks, based on the assumptions that tasks that need to be multitasked rely on independent resources, i.e., form a matching, and that tasks can be multitasked without interference if they form an induced matching. Our main result is an inherent tradeoff between the multitasking capacity and the average degree of the network that holds regardless of the network architecture. These results are also extended to networks of depth greater than 2. On the positive side, we demonstrate that networks that are random-like (e.g., locally sparse) can have desirable multitasking properties. 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.en_US
dc.format.extent2101 - 2110en_US
dc.relation.ispartofAdvances in Neural Information Processing Systemsen_US
dc.rightsFinal published version. This is an open access article.en_US
dc.titleA graph-theoretic approach to multitaskingen_US
dc.typeJournal Articleen_US

Files in This Item:
File Description SizeFormat 
6805-a-graph-theoretic-approach-to-multitasking (1).pdf269.14 kBAdobe PDFView/Download

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.