Algorithmic thresholds in combinatorial optimization depend on the time scaling

M. C. Angelini, M. Avila-González, F. D'Amico +3

In the last decades, many efforts have focused on analyzing typical-case hardness in optimization and inference problems. Some recent work has pointed out that polynomial algorithm…