INRC Forum: Bradley Theilman

Stochastic Neuromorphic Circuits for Solving MAXCUT

Abstract: Finding the maximum cut of a graph (MAXCUT) is a classic optimization problem that has motivated parallel algorithm development. In this talk, I will present two neuromorphic circuits that transform a source of randomness into computationally useful correlations for approximating solutions to graph MAXCUT. Neuromorphic computing has been successfully applied to various graph algorithms, by exploiting the analogy between a graph and the connectivity of a neural circuit. However, the physical constraints of neuromorphic hardware make translating an arbitrary graph into the neuromorphic domain challenging. Neuromorphic computing is also beginning to explore stochastic devices as efficient sources of randomness for large-scale stochastic algorithms. Graph MAXCUT is a well-known NP-complete discrete optimization problem with the best-known approximate solutions being stochastic algorithms, such as the Goemans-Williamson algorithm. I will show how to combine large-scale sources of intrinsic randomness with neuromorphic principles to implement two classes of stochastic approximations to graph MAXCUT in neuromorphic hardware. These approaches have architectural advantages over other neuromorphic graph algorithms and benefit from the theoretical performance guarantees of their algorithmic inspirations. I will show results from simulations of these circuits as well as results from an implementation of one of these circuits on Intel’s Loihi neuromorphic system. This work opens a new direction for stochastic neuromorphic circuits applied to discrete optimization.

Bio: Bradley Theilman is a postdoctoral appointee at Sandia National Laboratories. His research focuses on applying neuroscientific principles to neuromorphic computing. He earned a Ph.D. in computational neuroscience in 2021 from UC San Diego, where he worked on topological approaches to understanding neural population activity in the auditory regions of songbird brains in the laboratory of Dr. Tim Gentner.

For the meeting link, see the full INRC Forum Spring 2023 Schedule (accessible only to INRC Affiliates and Fully Engaged Members).