Low-Degree Hardness of Random Optimization Problems.

David Gamarnik Aukosh Jagannath Alexander S. Wein

Published in: FOCS (2020)

Keyphrases

low degree
optimization problems
agnostic learning
evolutionary algorithm
metaheuristic
uniform distribution
cost function
threshold functions
objective function
traveling salesman problem
noise tolerant
computational complexity
np hard
information theoretic
phase transition
decision lists