In the past decades, many efforts have focused on analyzing typical-case hardness in optimization and inference problems. Some recent work has pointed out that polynomial algorithms exist, running with a time that grows more than linearly with the system size, which can do better than linear algorithms, finding solutions to random problems in a wider range of parameters. However, a theory for polynomial and superlinear algorithms is in general lacking. Here, we examine the performance of the simulated annealing algorithm, a standard, versatile, and robust choice for solving optimization and inference problems, in the prototypical random 𝐾-SAT problem. For the first time, we show that the algorithmic thresholds depend on the time scaling of the algorithm with the size of the system. Indeed, one can identify not just one but different thresholds for linear, quadratic, and cubic regimes (and so on). This observation opens new directions in studying the typical case hardness in optimization problems.

Biography

Prof. Roberto Mulet works at the Center for Complex Systems and at the Department of Theoretical Physics of the University of Havana. His research work is concentrated on Statistical Physics, Soft Matter, Biological Physics, Nonlinear Dynamics and Theoretical Physics.

Inviter: Hai-Jun Zhou