Gap-preserving reductions and RE-completeness of independent set games

Laura Mančinska, Pieter Spaas, Taro Spirig +1

In complexity theory, gap-preserving reductions play a crucial role in studying hardness of approximation and in analyzing the relative complexity of multiprover interactive proof…