Hardness Amplification of Optimization Problems In this paper, we prove a general hardness amplification scheme for optimization problems based on the technique of direct products. We say that an optimization problem Pi is direct product feasible if it is possible to efficiently aggregate any k instances of Pi and form one large instance of Pi such that given an optimal feasible solution to the larger instance, we can efficiently find optimal feasible solutions to all the k smaller instances. Given a direct product feasible optimization problem Pi, our hardness amplification theorem may be informally stated as follows: If there is a distribution mathcalD over instances of Pi of size n such that every randomized algorithm running in time t(n) fails to solve Pi on frac1alpha(n) fraction of inputs sampled from mathcalD, then, assuming some relationships on alpha(n) and t(n), there is a distribution mathcalDu0027 over instances of Pi of size O(ncdot alpha(n)) such that every randomized algorithm running in time fract(n)poly(alpha(n)) fails to solve Pi on frac99100 fraction of inputs sampled from mathcalDu0027. As a consequence of the above theorem, we show hardness amplification of problems in various classes such as NPhard problems like MaxClique, Knapsack, and MaxSAT, problems in P such as Longest Common Subsequence, Edit Distance, Matrix Multiplication, and even problems in TFNP such as Factoring and computing Nash equilibrium.

Unifying computational entropies via KullbackLeibler divergence. We introduce KLhardness, a new notion of hardness for search problems which on the one hand is satisfied by all oneway functions and on the other hand implies both nextblock pseudoentropy and inaccessibleentropy, two forms of computational entropy used in recent constructions of pseudorandom generators and statistically hiding commitment schemes, respectively. Thus, KLhardness unifies the latter two notions of computational entropy and sheds light on the apparent duality between them. Additionally, it yields a more modular and illuminating proof that oneway functions imply nextblock inaccessible entropy, similar in structure to the proof that oneway functions imply nextblock pseudoentropy (Vadhan and Zheng, STOC u002712).