The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
作者： Dana Moshkovitz
DOI: 10.1007/978-3-642-32512-0_24
关键词:
摘要: We suggest the research agenda of establishing new hardness approximation results based on “projection games conjecture”, i.e., an instantiation Sliding Scale Conjecture Bellare, Goldwasser, Lund and Russell to projection games.
springer.com
core.ac.uk
springerlink.com参考文章(48)
Oded Regev, On the Complexity of Lattice Problems with Polynomial Approximation Factors The LLL Algorithm. pp. 475- 496 ,(2009) , 10.1007/978-3-642-02295-1_15
Subhash Khot, Inapproximability results for computational problems on lattices The LLL Algorithm. pp. 453- 473 ,(2009) , 10.1007/978-3-642-02295-1_14
Subhash Khot, Ashok Kumar Ponnuswami, Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion Automata, Languages and Programming. pp. 226- 237 ,(2006) , 10.1007/11786986_21
Daniele Micciancio, S. Goldwasser, Complexity of lattice problems : a cryptographic perspective Springer. ,(2002)
R. Impagliazzo, R. Paturi, Complexity of k-SAT conference on computational complexity. pp. 237- 240 ,(1999) , 10.1109/CCC.1999.766282
Ran Raz, A Parallel Repetition Theorem SIAM Journal on Computing. ,vol. 27, pp. 763- 803 ,(1998) , 10.1137/S0097539795280895
David Peleg, Approximation algorithms for the Label-CoverMAX and Red-Blue Set Cover problems Journal of Discrete Algorithms. ,vol. 5, pp. 55- 64 ,(2007) , 10.1016/J.JDA.2006.03.008
Russell Impagliazzo, Ramamohan Paturi, On the complexity of K -SAT conference on computational complexity. ,vol. 62, pp. 367- 375 ,(2001) , 10.1006/JCSS.2000.1727
Marek Cygan, Łukasz Kowalik, Mateusz Wykurz, Exponential-time approximation of weighted set cover Information Processing Letters. ,vol. 109, pp. 957- 961 ,(2009) , 10.1016/J.IPL.2009.05.003
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra, PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability Computational Complexity. ,vol. 20, pp. 413- 504 ,(2011) , 10.1007/S00037-011-0014-4