Low-Degree Hardness of Random Optimization Problems.

David Gamarnik Aukosh Jagannath Alexander S. Wein

Published in: CoRR (2020)

Keyphrases

low degree
optimization problems
evolutionary algorithm
agnostic learning
metaheuristic
cost function
uniform distribution
threshold functions
objective function
model selection
np hard
traveling salesman problem
theoretical analysis
target function
error rate
lower bound
computational complexity