Using synchronized oscillators to compute the maximum independent set

Antik Mallick; Mohammad Khairul Bashar; Daniel S. Truesdell; Benton H. Calhoun; Siddharth Joshi; Nikhil Shukla

doi:10.1038/s41467-020-18445-1

Nature Communications (Sep 2020)

Using synchronized oscillators to compute the maximum independent set

Antik Mallick,
Mohammad Khairul Bashar,
Daniel S. Truesdell,
Benton H. Calhoun,
Siddharth Joshi,
Nikhil Shukla

Affiliations

Antik Mallick: Department of Electrical and Computer Engineering, University of Virginia
Mohammad Khairul Bashar: Department of Electrical and Computer Engineering, University of Virginia
Daniel S. Truesdell: Department of Electrical and Computer Engineering, University of Virginia
Benton H. Calhoun: Department of Electrical and Computer Engineering, University of Virginia
Siddharth Joshi: Department of Computer Science and Engineering, University of Notre Dame
Nikhil Shukla: Department of Electrical and Computer Engineering, University of Virginia

DOI: https://doi.org/10.1038/s41467-020-18445-1
Journal volume & issue: Vol. 11, no. 1
pp. 1 – 7

Abstract

Read online

Designing efficient analog dynamical systems for solving hard optimization problems remains a challenge. Here, the authors demonstrate a dynamical system of thirty oscillators with reconfigurable coupling to compute optimal/near-optimal solutions to the hard Maximum Independent Set problem with over 90% accuracy.

Published in Nature Communications

ISSN: 2041-1723 (Online)
Publisher: Nature Portfolio
Country of publisher: United Kingdom
LCC subjects: Science
Website: https://www.nature.com/ncomms/

About the journal