How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs
Loading...
Official URL
Full text at PDC
Publication date
2021
Authors
Bernaschi, M.
Bisson, M.
Fatica, M.
Marinari, E.
Parisi, G.
Ricci-Tersenghi, F.
Advisors (or tutors)
Editors
Journal Title
Journal ISSN
Volume Title
Publisher
EPL Association, European Physical Society
Citations
Exportar
Citation
Abstract
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
Description
© 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.