<p>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. </p>

CC BY-SA 4.0
2019-06-20T19:01:16.433Z
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
CC BY-SA 4.0
2019-06-23T14:16:44.587Z
@YonatanN That's a great example. I would accept it as an answer if you want to copy paste it.
Elliot Gorokhovsky
<cc.complexity-theory><approximation-algorithms><approximation-hardness>
Example of a hardness-of-approximation proof which improves the approximation factor?
Elliot Gorokhovsky
# Example of a hardness-of-approximation proof which improves the approximation factor?

(Asked by: username_0 on 2019-06-20)

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.

**Tags:** cc.complexity-theory, approximation-algorithms, approximation-hardness

> **Comments:**
> **username_1**: 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.  
> **username_0**: @YonatanN That's a great example. I would accept it as an answer if you want to copy paste it.  

---

## 0 answers

