3-bit dictator testing: 1 vs. 5/8

ABSTRACT

In the conclusion of his monumental paper on optimal inapproximability results, Håstad [13] suggested that Fourier analysis of Dictator (Long Code) Tests may not be universally applicable in the study of CSPs. His main open question was to determine if the technique could resolve the approximability of satisfiable 3-bit constraint satisfaction problems. In particular, he asked if the "Not Two" (NTW) predicate is non-approximable beyond the random assignment threshold of 5/8 on satisfiable instances. Around the same time, Zwick [30] showed that all satisfiable 3-CSPs are 5/8-approximable and conjectured that the 5/8 is optimal.

In this work we show that Fourier analysis techniques can produce a Dictator Test based on NTW with completeness 1 and soundness 5/8. Our test's analysis uses the Bonami-Gross-Beckner hypercontractive inequality. We also show a soundness lower bound of 5/8 for all 3-query Dictator Tests with perfect completeness. This lower bound for Property Testing is proved in part via a semidefinite programming algorithm of Zwick [30].

Our work precisely determines the 3-query "Dictatorship Testing gap". Although this represents progress on Zwick's conjecture, current PCP "outer verifier" technology is insufficient to convert our Dictator Test into an NP-hardness-of-approximation result.

REFERENCES

• 1: 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]
• 2: Manuel Blum , Michael Luby , Ronitt Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, v.47 n.3, p.549-595, Dec. 1993 [doi>10.1016/0022-0000(93)90044-W]
• 3: A. Bonami. Ensembles Λ(p) dans le dual de D^∞. Ann. Inst. Fourier, 18(2):193--204, 1968.
• 4: Irit Dinur, The PCP theorem by gap amplification, Journal of the ACM (JACM), v.54 n.3, p.12-es, June 2007 [doi>10.1145/1236457.1236459]
• 5: Lars Engebretsen , Jonas Holmerin, Three-query PCPs with perfect completeness over non-Boolean domains, Random Structures & Algorithms, v.27 n.1, p.46-75, August 2005 [doi>10.1002/rsa.v27:1]
• 6: M. Furst, J. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory, 17(1):13--27, 1984.
• 7: B. Green. Finite field models in additive combinatorics. In London Mathematical Society Lecture Note Series, Cambridge University Press, volume 324. 2005.
• 8: L. Gross. Logarithmic Sobolev inequalities. Amer. J. Math., 97:1061--1083, 1975.
• 9: 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]
• 10: 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.
• 11: Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
• 12: J. Håastad. Clique is hard to approximate within n^{1 - ε}. Acta Mathematica, 182(1):105--142, 1999.
• 13: 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]
• 14: J. Håastad. On nontrivial approximations of CSPs, 2006. http://www.nada.kth.se/~johanh/approx06.pdf. Invited address at APPROX.
• 15: 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
• 16: 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]
• 17: 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]
• 18: 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]
• 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: Subhash A. Khot , Nisheeth K. Vishnoi, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.53-62, October 23-25, 2005 [doi>10.1109/SFCS.2005.74]
• 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. www.cs.cmu.edu/~odonnell/booleananalysis/lecture4.pdf.
• 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: Michal Parnas , Dana Ron , Alex Samorodnitsky, Testing Basic Boolean Formulae, SIAM Journal on Discrete Mathematics, v.16 n.1, p.20-46, 2003 [doi>10.1137/S0895480101407444]
• 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: Alex Samorodnitsky , Luca Trevisan, Gowers uniformity, influence of variables, and PCPs, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132519]
• 27: D. Stefankovic. Fourier transforms in computer science. Master's thesis, University of Chicago, 2002.
• 28: L. Trevisan. Approximating satisfiable satisfiability problems. Algorithmica, 28(1):145--172, 2000.
• 29: 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]
• 30: 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
• 31: 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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General