Show simple item record

dc.contributor.authorLynch, Nancy Ann
dc.contributor.authorMusco, Cameron Nicholas
dc.contributor.authorParter, Merav
dc.date.accessioned2022-07-18T17:56:29Z
dc.date.available2021-09-20T18:21:17Z
dc.date.available2022-07-18T17:56:29Z
dc.date.issued2017
dc.identifier.urihttps://hdl.handle.net/1721.1/132184.2
dc.description.abstractWe initiate a line of investigation into biological neural networks from an algorithmic perspective. We develop a simplified but biologically plausible model for distributed computation in stochastic spiking neural networks and study tradeoffs between computation time and network complexity in this model. Our aim is to abstract real neural networks in a way that, while not capturing all interesting features, preserves high-level behavior and allows us to make biologically relevant conclusions. In this paper, we focus on the important 'winner-Take-All' (WTA) problem, which is analogous to a neural leader election unit: A network consisting of n input neurons and n corresponding output neurons must converge to a state in which a single output corresponding to a firing input (the 'winner') fires, while all other outputs remain silent. Neural circuits for WTA rely on inhibitory neurons, which suppress the activity of competing outputs and drive the network towards a converged state with a single firing winner. We attempt to understand how the number of inhibitors used affects network convergence time. We show that it is possible to significantly outperform naive WTA constructions through a more refined use of inhibition, solving the problem in O(θ) rounds in expectation with just O(log1/θ n) inhibitors for any θ. An alternative construction gives convergence in O(log1/θ n) rounds with O(θ) inhibitors. We complement these upper bounds with our main technical contribution, a nearly matching lower bound for networks using ≥ log log n inhibitors. Our lower bound uses familiar indistinguishability and locality arguments from distributed computing theory applied to the neural setting. It lets us derive a number of interesting conclusions about the structure of any network solving WTA with good probability, and the use of randomness and inhibition within such a network.en_US
dc.language.isoen
dc.relation.isversionof10.4230/LIPIcs.ITCS.2017.15en_US
dc.rightsCreative Commons Attribution 4.0 International licenseen_US
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/en_US
dc.sourceDROPSen_US
dc.titleComputational tradeoffs in biological neural networks: Self-stabilizing winner-Take-All networksen_US
dc.typeArticleen_US
dc.contributor.departmentMassachusetts Institute of Technology. Department of Electrical Engineering and Computer Scienceen_US
dc.contributor.departmentMassachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratoryen_US
dc.eprint.versionFinal published versionen_US
dc.type.urihttp://purl.org/eprint/type/ConferencePaperen_US
eprint.statushttp://purl.org/eprint/status/NonPeerRevieweden_US
dc.date.updated2019-06-13T16:28:21Z
dspace.date.submission2019-06-13T16:28:22Z
mit.metadata.statusPublication Information Neededen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

VersionItemDateSummary

*Selected version