How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs

Thumbnail Image
Full text at PDC
Publication Date
Bernaschi, M.
Bisson, M.
Fatica, M.
Marinari, E.
Parisi, G.
Ricci-Tersenghi, F.
Advisors (or tutors)
Journal Title
Journal ISSN
Volume Title
EPL Association, European Physical Society
Google Scholar
Research Projects
Organizational Units
Journal Issue
A recent 3-XORSAT challenge required to minimize a very complex and rough energy function, typical of glassy models with a random first-order transition and a golf-course-like energy landscape. We present the ideas beyond the quasi-greedy algorithm and its very efficient implementation on GPUs that are allowing us to rank first in such a competition. We suggest a better protocol to compare algorithmic performances and we also provide analytical predictions about the exponential growth of the times to find the solution in terms of free-energy barriers. Copyright (C) 2021 EPLA
© 2021 EPLA. We are grateful to Itay Hen for the helpful discussions. This work was supported by MINECO (Spain) through Grant No. PGC2018-094684-B-C21 (partially funded by FEDER) and the European Research Council under the European Union’s Horizon 2020 research and innovation program (Grant No. 694925-Lotglassy). This research used resources of the Oak Ridge Leadership Computing Facility at the Oak Ridge National Laboratory, which is supported by the Office of Science of the U.S. Department of Energy under Contract No. DE-AC05-00OR22725.
Unesco subjects