Reviews: Computational Separations between Sampling and Optimization

The goal is to show that under some situations, one of these problems is easy and the other is hard. To show that optimization can be harder than sampling, the construction hides the solution of an NP-hard problem as a small bump in a mostly flat function. Thus, approximate sampling is easy (the distribution is mostly uniform), but optimization would result in solving an NP-hard problem. To show that sampling can be harder than optimization, the construction amplifies the number of solutions of an NP-hard problem and plants an additional simple solution, and then encodes this into a function that is flat in many places, but has bumps at every possible solution of the NP-hard problem. Optimization is as easy as finding the planted simple solution, but, intuitively, sampling requires finding many of the hard solutions.