Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics.
David GamarnikAukosh JagannathAlexander S. WeinPublished in: SIAM J. Comput. (2024)
Keyphrases
- low degree
- optimization problems
- threshold functions
- uniform distribution
- learning dnf
- agnostic learning
- boolean functions
- evolutionary algorithm
- metaheuristic
- cost function
- objective function
- pac learning
- membership queries
- random instances
- target concept
- phase transition
- learning theory
- pairwise
- target function
- linear threshold
- computational complexity