{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T16:19:01Z","timestamp":1784218741471,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":42,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,6]],"date-time":"2021-07-06T00:00:00Z","timestamp":1625529600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Department of Energy","award":["DE-NA0003525"],"award-info":[{"award-number":["DE-NA0003525"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,6]]},"DOI":"10.1145\/3409964.3461813","type":"proceedings-article","created":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T23:07:02Z","timestamp":1625094422000},"page":"35-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Provable Advantages for Graph Algorithms in Spiking Neural Networks"],"prefix":"10.1145","author":[{"given":"James B.","family":"Aimone","sequence":"first","affiliation":[{"name":"Sandia National Laboratories, Albuquerque, NM, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yang","family":"Ho","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Albuquerque, NM, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ojas","family":"Parekh","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Albuquerque, NM, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cynthia A.","family":"Phillips","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Albuquerque, NM, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ali","family":"Pinar","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Livermore, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"William","family":"Severa","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Albuquerque, NM, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yipu","family":"Wang","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Albuquerque, NM, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,7,6]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Energy scaling advantages of resistive memory crossbar based computation and its application to sparse coding. Frontiers in neuroscience 9","author":"Agarwal S.","year":"2015","unstructured":"Agarwal , S. , Quach , T.-T. , Parekh , O. , Hsia , A. H. , DeBenedictis , E. P. , James , C. D. , Marinella , M. J. , and Aimone , J. B . Energy scaling advantages of resistive memory crossbar based computation and its application to sparse coding. Frontiers in neuroscience 9 ( 2015 ). Agarwal, S., Quach, T.-T., Parekh, O., Hsia, A. H., DeBenedictis, E. P., James, C. D., Marinella, M. J., and Aimone, J. B. Energy scaling advantages of resistive memory crossbar based computation and its application to sparse coding. Frontiers in neuroscience 9 (2015)."},{"key":"e_1_3_2_1_2_1","first-page":"1307","volume-title":"IEEE International Sympoisum on Circuits and Systems (June","volume":"3","author":"Aibara R.","year":"1991","unstructured":"Aibara , R. , Mitsui , Y. , and Ae , T . A CMOS chip design of binary neural network with delayed synapses. In 1991 ., IEEE International Sympoisum on Circuits and Systems (June 1991 ), pp. 1307 -- 1310 vol. 3 . Aibara, R., Mitsui, Y., and Ae, T. A CMOS chip design of binary neural network with delayed synapses. In 1991., IEEE International Sympoisum on Circuits and Systems (June 1991), pp. 1307--1310 vol.3."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3231589"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3354265.3354285"},{"key":"e_1_3_2_1_5_1","volume-title":"A spiking neural algorithm for the network flow problem","author":"Ali A.","year":"2019","unstructured":"Ali , A. , and Kwisthout , J . A spiking neural algorithm for the network flow problem , 2019 . Ali, A., and Kwisthout, J. A spiking neural algorithm for the network flow problem, 2019."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2017.781"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/cne.21974"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2014.2313565"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-008-0082-9"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2018.112130359"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.15388\/ioi.2018.03"},{"key":"e_1_3_2_1_12_1","volume-title":"Parity, circuits, and the polynomial-time hierarchy. Mathematical systems theory 17, 1 (Dec","author":"Furst M.","year":"1984","unstructured":"Furst , M. , Saxe , J. B. , and Sipser , M . Parity, circuits, and the polynomial-time hierarchy. Mathematical systems theory 17, 1 (Dec . 1984 ), 13--27. Furst, M., Saxe, J. B., and Sipser, M. Parity, circuits, and the polynomial-time hierarchy. Mathematical systems theory 17, 1 (Dec. 1984), 13--27."},{"key":"e_1_3_2_1_13_1","volume-title":"New distributed algorithms in almost mixing time via transformations from parallel algorithms","author":"Ghaffari M.","year":"2018","unstructured":"Ghaffari , M. , and Li , J . New distributed algorithms in almost mixing time via transformations from parallel algorithms , 2018 . Ghaffari, M., and Li, J. New distributed algorithms in almost mixing time via transformations from parallel algorithms, 2018."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/171479.171481"},{"key":"e_1_3_2_1_15_1","volume-title":"Spike-based primitives for graph algorithms","author":"Hamilton K. E.","year":"2019","unstructured":"Hamilton , K. E. , Mintz , T. M. , and Schuman , C. D . Spike-based primitives for graph algorithms , 2019 . Hamilton, K. E., Mintz, T. M., and Schuman, C. D. Spike-based primitives for graph algorithms, 2019."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neuron.2017.06.011"},{"key":"e_1_3_2_1_17_1","volume-title":"34th International Symposium on Distributed Computing (DISC 2020)","author":"Hitron Y.","year":"2020","unstructured":"Hitron , Y. , Musco , C. , and Parter , M . Spiking neural networks through the lens of streaming algorithms . In 34th International Symposium on Distributed Computing (DISC 2020) ( 2020 ), Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik. Hitron, Y., Musco, C., and Parter, M. Spiking neural networks through the lens of streaming algorithms. In 34th International Symposium on Distributed Computing (DISC 2020) (2020), Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_1_18_1","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"1","volume-title":"27th Annual European Symposium on Algorithms (ESA 2019) (Dagstuhl","author":"Hitron Y.","year":"2019","unstructured":"Hitron , Y. , and Parter , M . Counting to Ten with Two Fingers: Compressed Counting with Spiking Neurons . In 27th Annual European Symposium on Algorithms (ESA 2019) (Dagstuhl , Germany, 2019 ), M. A. Bender, O. Svensson, and G. Herman, Eds., vol. 144 of Leibniz International Proceedings in Informatics (LIPIcs) , Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik , pp. 57: 1 -- 57 :17. Hitron, Y., and Parter, M. Counting to Ten with Two Fingers: Compressed Counting with Spiking Neurons. In 27th Annual European Symposium on Algorithms (ESA 2019) (Dagstuhl, Germany, 2019), M. A. Bender, O. Svensson, and G. Herman, Eds., vol. 144 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, pp. 57:1--57:17."},{"key":"e_1_3_2_1_19_1","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"1","volume-title":"11th Innovations in Theoretical Computer Science Conference (ITCS 2020) (Dagstuhl","author":"Hitron Y.","year":"2020","unstructured":"Hitron , Y. , Parter , M. , and Perri , G . The Computational Cost of Asynchronous Neural Communication . In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) (Dagstuhl , Germany, 2020 ), T. Vidick, Ed., vol. 151 of Leibniz International Proceedings in Informatics (LIPIcs) , Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik , pp. 48: 1 -- 48 :47. Hitron, Y., Parter, M., and Perri, G. The Computational Cost of Asynchronous Neural Communication. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) (Dagstuhl, Germany, 2020), T. Vidick, Ed., vol. 151 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, pp. 48:1--48:47."},{"key":"e_1_3_2_1_20_1","unstructured":"H\u00f6ppner S. Partzsch J. Mayr C. and Furber S. Spinnaker2 - an energy efficient realtime neuromorphic compute system in 22fdx technology. https:\/\/community.arm.com\/cfs-file\/__key\/communityserver-blogs-components-weblogfiles\/00-00-00--37--98\/Sebastian-Hoppner-_2D00_-Neural-Networks-.pdf.  H\u00f6ppner S. Partzsch J. Mayr C. and Furber S. Spinnaker2 - an energy efficient realtime neuromorphic compute system in 22fdx technology. https:\/\/community.arm.com\/cfs-file\/__key\/communityserver-blogs-components-weblogfiles\/00-00-00--37--98\/Sebastian-Hoppner-_2D00_-Neural-Networks-.pdf."},{"key":"e_1_3_2_1_21_1","unstructured":"Intel core i7--9700t specifications. https:\/\/www.intel.com\/content\/www\/us\/en\/products\/processors\/core\/i7-processors\/i7--9700t.html.  Intel core i7--9700t specifications. https:\/\/www.intel.com\/content\/www\/us\/en\/products\/processors\/core\/i7-processors\/i7--9700t.html."},{"key":"e_1_3_2_1_22_1","unstructured":"Intel scales neuromorphic research system to 100 million neurons. https:\/\/newsroom.intel.com\/news\/intel-scales-neuromorphic-research-system-100-million-neurons.  Intel scales neuromorphic research system to 100 million neurons. https:\/\/newsroom.intel.com\/news\/intel-scales-neuromorphic-research-system-100-million-neurons."},{"key":"e_1_3_2_1_23_1","volume-title":"Encyclopedia of Computer Science and Technology","author":"Kent A.","year":"1992","unstructured":"Kent , A. , and Williams , J. G. , Eds . Encyclopedia of Computer Science and Technology . Marcel Dekker, Inc. , 1992 . Volume 26, Supplement 11. Kent, A., and Williams, J. G., Eds. Encyclopedia of Computer Science and Technology. Marcel Dekker, Inc., 1992. Volume 26, Supplement 11."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/IJCNN.2008.4634199"},{"key":"e_1_3_2_1_25_1","volume-title":"On the computational power and complexity of Spiking Neural Networks. arXiv:2001.08439 [cs] (Jan","author":"Kwisthout J.","year":"2020","unstructured":"Kwisthout , J. , and Donselaar , N . On the computational power and complexity of Spiking Neural Networks. arXiv:2001.08439 [cs] (Jan . 2020 ). arXiv: 2001.08439. Kwisthout, J., and Donselaar, N. On the computational power and complexity of Spiking Neural Networks. arXiv:2001.08439 [cs] (Jan. 2020). arXiv: 2001.08439."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1996.8.1.1"},{"key":"e_1_3_2_1_27_1","volume-title":"Spinnaker 2: A 10 million core processor system for brain simulation and machine learning","author":"Mayr C.","year":"2019","unstructured":"Mayr , C. , Hoeppner , S. , and Furber , S . Spinnaker 2: A 10 million core processor system for brain simulation and machine learning , 2019 . Mayr, C., Hoeppner, S., and Furber, S. Spinnaker 2: A 10 million core processor system for brain simulation and machine learning, 2019."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1254642"},{"key":"e_1_3_2_1_29_1","unstructured":"Moore S. Intel's Neuromorphic System Hits 8 Million Neurons 100 Million Coming by 2020 - IEEE Spectrum. https:\/\/spectrum.ieee.org\/tech-talk\/artificial-intelligence\/embedded-ai\/intels-neuromorphic-system-hits-8-million-neurons-100-million-coming-by-2020.  Moore S. Intel's Neuromorphic System Hits 8 Million Neurons 100 Million Coming by 2020 - IEEE Spectrum. https:\/\/spectrum.ieee.org\/tech-talk\/artificial-intelligence\/embedded-ai\/intels-neuromorphic-system-hits-8-million-neurons-100-million-coming-by-2020."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591850"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSSC.2013.2259038"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210410"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.817389"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCAS.2010.5536970"},{"key":"e_1_3_2_1_35_1","volume-title":"A survey of neuromorphic computing and neural networks in hardware. arXiv preprint arXiv:1705.06963","author":"Schuman C. D.","year":"2017","unstructured":"Schuman , C. D. , Potok , T. E. , Patton , R. M. , Birdwell , J. D. , Dean , M. E. , Rose , G. S. , and Plank , J. S . A survey of neuromorphic computing and neural networks in hardware. arXiv preprint arXiv:1705.06963 ( 2017 ). Schuman, C. D., Potok, T. E., Patton, R. M., Birdwell, J. D., Dean, M. E., Rose, G. S., and Plank, J. S. A survey of neuromorphic computing and neural networks in hardware. arXiv preprint arXiv:1705.06963 (2017)."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404038"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.106225"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/IJCNN.2013.6706927"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804401"},{"key":"e_1_3_2_1_40_1","volume-title":"The computer and the brain","author":"Von Neumann J.","year":"2012","unstructured":"Von Neumann , J. The computer and the brain . Yale University Press , 2012 . Von Neumann, J. The computer and the brain. Yale University Press, 2012."},{"key":"e_1_3_2_1_41_1","first-page":"12","article-title":"General-purpose computation with neural networks: A survey of complexity theoretic results","volume":"15","author":"S'ima J.","year":"2003","unstructured":"v S'ima , J. , and Orponen , P . General-purpose computation with neural networks: A survey of complexity theoretic results . Neural Comput. 15 , 12 ( Dec. 2003 ), 2727--2778. vS'ima, J., and Orponen, P. General-purpose computation with neural networks: A survey of complexity theoretic results. Neural Comput. 15, 12 (Dec. 2003), 2727--2778.","journal-title":"Neural Comput."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.49"}],"event":{"name":"SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures","location":"Virtual Event USA","acronym":"SPAA '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3409964.3461813","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/abs\/10.1145\/3409964.3461813","content-type":"text\/html","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3409964.3461813","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3409964.3461813","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:08Z","timestamp":1750191428000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3409964.3461813"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,6]]},"references-count":42,"alternative-id":["10.1145\/3409964.3461813","10.1145\/3409964"],"URL":"https:\/\/doi.org\/10.1145\/3409964.3461813","relation":{},"subject":[],"published":{"date-parts":[[2021,7,6]]},"assertion":[{"value":"2021-07-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}