The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
We suggest the research agenda of establishing new hardness of approximation results based on the “projection games conjecture”, i.e., an instantiation of the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell to projection games. We pursue this line of research by establishing a tig...
Main Author: | Moshkovitz Aaronson, Dana Hadar |
---|---|
Other Authors: | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
Format: | Article |
Language: | en_US |
Published: |
Springer-Verlag
2014
|
Online Access: | http://hdl.handle.net/1721.1/90484 https://orcid.org/0000-0002-5157-8086 |
Similar Items
-
NP-Hardness of Approximately Solving Linear Equations Over Reals
by: Khot, Subhash, et al.
Published: (2011) -
Improved Approximation Algorithms for Projection Games
by: Manurangsi, Pasin, et al.
Published: (2014) -
Improved Approximation Algorithms for Projection Games
by: Manurangsi, Pasin, et al.
Published: (2017) -
Parallel Repetition From Fortification
by: Moshkovitz Aaronson, Dana Hadar
Published: (2014) -
Approximation algorithms for NP-hard problems /
by: Hochbaum, Dorit (Dorit S.)
Published: (1997)