How we are leading a 3-XORSAT challenge: From the energy landscape to the algorithm and its efficient implementation on GPUsContribution to the Focus Issue Progress on Statistical Physics and Complexity edited by Roberta Citro, Giorgio Kaniadakis, Claudio Guarcello, Antonio Maria Scarfone and Davide Valenti. (13th May 2021) - Bernaschi, M.; Bisson, M.; Fatica, M.; Marinari, E.; Martin-Mayor, V.; Parisi, G.; Ricci-Tersenghi, F.
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.