Improved Approximation Algorithms for Projection Games
The projection games (aka Label Cover) problem is of great importance to the field of approximation algorithms, since most of the NP-hardness of approximation results we know today are reductions from Label Cover. In this paper we design several approximation algorithms for projection games: (1) A p...
Main Authors: | Manurangsi, Pasin, Moshkovitz Aaronson, Dana Hadar |
---|---|
Other Authors: | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
Format: | Article |
Language: | English |
Published: |
Springer US
2017
|
Online Access: | http://hdl.handle.net/1721.1/106639 https://orcid.org/0000-0002-5157-8086 |
Similar Items
-
Improved Approximation Algorithms for Projection Games
by: Manurangsi, Pasin, et al.
Published: (2014) -
The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
by: Moshkovitz Aaronson, Dana Hadar
Published: (2014) -
On approximating projection games
by: Manurangsi, Pasin
Published: (2016) -
NP-Hardness of Approximately Solving Linear Equations Over Reals
by: Khot, Subhash, et al.
Published: (2011) -
Parallel Repetition From Fortification
by: Moshkovitz Aaronson, Dana Hadar
Published: (2014)