Conditional hardness for satisfiable 3-CSPs

ABSTRACT

In this paper we study a fundamental open problem in the area of probabilistic checkable proofs: What is the smallest s such that NP ⊆ naPCP1,s[O(log n),3]? In the language of hardness of approximation, this problem is equivalent to determining the smallest s such that getting an s-approximation for satisfiable 3-bit constraint satisfaction problems ("3-CSPs") is NP-hard. The previous best upper bound and lower bound for s are 20/27+µ by Khot and Saket [KS06], and 5/8 (assuming NP subseteq BPP) by Zwick [Zwi98]. In this paper we close the gap assuming Khot's d-to-1 Conjecture. Formally, we prove that if Khot's d-to-1 Conjecture holds for any finite constant integer d, then NP naPCP_{1,5/8+ µ}[O(log n),3] for any constant µ > 0. Our conditional result also solves Hastad's open question [Has01] on determining the inapproximability of satisfiable Max-NTW ("Not Two") instances and confirms Zwick's conjecture [Zwi98] that the 5/8-approximation algorithm for satisfiable 3-CSPs is optimal.

REFERENCES

• 1: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 2: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 3: Per Austrin, Balanced max 2-sat might not be the hardest, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250818]
• 4: Mihir Bellare , Oded Goldreich , Madhu Sudan, Free Bits, PCPs, and Nonapproximability---Towards Tight Results, SIAM Journal on Computing, v.27 n.3, p.804-915, June 1998 [doi>10.1137/S0097539796302531]
• 5: A. Bonami. Ensembles (p) dans le dual de D. Ann. Inst. Fourier, 18(2):193--204, 1968.
• 6: Nadia Creignou, A dichotomy theorem for maximum generalized satisfiability problems, Journal of Computer and System Sciences, v.51 n.3, p.511-522, Dec. 1995 [doi>10.1006/jcss.1995.1087]
• 7: Nadia Creignou , Sanjeev Khanna , Madhu Sudan, Complexity classifications of boolean constraint satisfaction problems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
• 8: Irit Dinur , Elchanan Mossel , Oded Regev, Conditional hardness for approximate coloring, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132567]
• 9: L. Gross. Logarithmic Sobolev inequalities. Amer. J. Math., 97:1061--1083, 1975.
• 10: Venkatesan Guruswami , Subhash Khot, Hardness of Max 3SAT with No Mixed Clauses, Proceedings of the 20th Annual IEEE Conference on Computational Complexity, p.154-162, June 11-15, 2005 [doi>10.1109/CCC.2005.10]
• 11: V. Guruswami, D. Lewin, M. Sudan, and L. Trevisan. A tight characterization of NP with 3 query PCPs. Electronic Colloq. on Comp. Complexity (ECCC), 5(34), 1998.
• 12: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 13: J. Hastad and S. Khot. Query efficient PCPs with perfect completeness. Theory of Computing, 1(1):119--148, 2005.
• 14: Howard Karloff , Uri Zwick, A 7/8-Approximation Algorithm for MAX 3SAT?, Proceedings of the 38th Annual Symposium on Foundations of Computer Science, p.406, October 19-22, 1997
• 15: Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510017]
• 16: Subhash Khot , Guy Kindler , Elchanan Mossel , Ryan O’Donnell, Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?, SIAM Journal on Computing, v.37 n.1, p.319-357, April 2007 [doi>10.1137/S0097539705447372]
• 17: Subhash Khot , Ryan O'Donnell, SDP gaps and UGC-hardness for MAXCUTGAIN, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.217-226, October 21-24, 2006 [doi>10.1109/FOCS.2006.67]
• 18: Subhash Khot , Oded Regev, Vertex cover might be hard to approximate to within 2-ε, Journal of Computer and System Sciences, v.74 n.3, p.335-349, May, 2008 [doi>10.1016/j.jcss.2007.06.019]
• 19: Subhash Khot , Rishi Saket, A 3-Query Non-Adaptive PCP with Perfect Completeness, Proceedings of the 21st Annual IEEE Conference on Computational Complexity, p.159-169, July 16-20, 2006 [doi>10.1109/CCC.2006.5]
• 20: Elchanan Mossel, Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.156-165, October 25-28, 2008 [doi>10.1109/FOCS.2008.44]
• 21: Elchanan Mossel , Ryan O'Donnell , Krzysztof Oleszkiewicz, Noise stability of functions with low in.uences invariance and optimality, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.21-30, October 23-25, 2005 [doi>10.1109/SFCS.2005.53]
• 22: R. O'Donnell. Analysis of boolean functions lecture notes, 2007. http://www.cs.cmu.edu/ odonnell/boolean-analysis/.
• 23: Ryan O'Donnell , Yi Wu, An optimal sdp algorithm for max-cut, and equally optimal long code tests, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374425]
• 24: Ryan O'Donnell , Yi Wu, 3-bit dictator testing: 1 vs. 5/8, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.365-373, January 04-06, 2009, New York, New York
• 25: Prasad Raghavendra, Optimal algorithms and inapproximability results for every CSP?, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374414]
• 26: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 27: Alex Samorodnitsky , Luca Trevisan, A PCP characterization of NP with optimal amortized query complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.191-199, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335329]
• 28: Luca Trevisan , Gregory B. Sorkin , Madhu Sudan , David P. Williamson, Gadgets, Approximation, and Linear Programming, SIAM Journal on Computing, v.29 n.6, p.2074-2097, April 2000 [doi>10.1137/S0097539797328847]
• 29: Uri Zwick, Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.201-210, January 25-27, 1998, San Francisco, California, United States
• 30: Uri Zwick, Computer assisted proof of optimal approximability results, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.496-505, January 06-08, 2002, San Francisco, California

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
PCP, hardness of approximation, khot's, satisfiable 3-CSPs