Computational Hardness in Random Optimization Problems from the Overlap Gap Property
We study the limits of efficient algorithms in random optimization problems. In these problems, we are given a random objective function and our goal is to find an input achieving a large output. These problems often exhibit information-computation gaps, where the maximum objective that exists is la...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/143164 |