# Example of a hardness-of-approximation proof which improves the approximation factor?

Are there any examples of hardness-of-approximation reductions where we get a better hardness bound for the problem we've reduced to than the problem we've reduced from? In the examples I've seen so far, the bound is usually degraded in the reduction.

• A lot of reductions amplify hardness by toying with the objective function. For example, Min Circuit SAT (given a Boolean circuit, what is the smallest hamming-weight input that evaluates to true) is NP-hard because it can encode min vertex cover. This gives a small hardness factor of ~2. So it's hard to distinguish instances that can be solved with weight a=f(n) from those with weight 1.5a. But now we can reduce from this circuit sat instance by making the circuit that accepts either solutions to the original CSAT instance of weight <= a, or anything of weight > n/2, for $\omega(1)$ hardness. – Yonatan N Jun 20 '19 at 19:01
• @YonatanN That's a great example. I would accept it as an answer if you want to copy paste it. – Elliot Gorokhovsky Jun 23 '19 at 14:16