Construction of Optimal Gadget Reductions

Abstract:

Reductions have played an important role in theoretical computer science since the development of the theory of NP-completeness. They have also been used in the domain of approximation algorithms. One such use is to transfer lower bounds, usually derived from probabilistic proof systems, from the original problem to other problems. In this context the cost of the reduction is important - a smaller cost leads to a stronger inapproximability result. In this talk we discuss the problem of finding the cheapest reductions and focus on the class of gadget reductions. It turns out that it in many cases is possible to obtain the best possible reductions by solving linear programs. Many strong inapproximability results have been derived using this technique.