Randomly supported independence and resistance

ABSTRACT

We prove that for any positive integer k, there is a constant c_k such that a randomly selected set of c_k n^k log n Boolean vectors with high probability supports a balanced k-wise independent distribution. In the case of k ≤ 2 a more elaborate argument gives the stronger bound c_k n^k. Using a recent result by Austrin and Mossel this shows that a predicate on t bits, chosen at random among predicates accepting c₂ t² input vectors, is, assuming the Unique Games Conjecture, likely to be approximation resistant. These results are close to tight: we show that there are other constants, c_k', such that a randomly selected set of cardinality c_k' n^k points is unlikely to support a balanced k-wise independent distribution and, for some c>0, a random predicate accepting ct²/log t input vectors is non-trivially approximable with high probability. In a different application of the result of Austrin and Mossel we prove that, again assuming the Unique Games Conjecture, any predicate on t bits accepting at least (32/33) • 2^t inputs is approximation resistant. The results extend from the Boolean domain to larger finite domains.

REFERENCES

• 1: Sanjeev Arora , Subhash A. Khot , Alexandra Kolla , David Steurer , Madhur Tulsiani , Nisheeth K. Vishnoi, Unique games on expanding constraint graphs are easy: extended abstract, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374380]
• 2: P. Austrin. Conditional Inapproximability and Limited Independence. PhD thesis, KTH -- Royal Institute of Technology, 2008.
• 3: Per Austrin , Elchanan Mossel, Approximation Resistant Predicates from Pairwise Independence, Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity, p.249-258, June 22-26, 2008 [doi>10.1109/CCC.2008.20]
• 4: W. Beckner. Inequalities in Fourier analysis. Annals of Mathematics, 102(1):159--182, 1975.
• 5: A. Bonami. Etude des coefficients de Fourier des fonctions de Lp(G). Ann. Inst. Fourier, 20:335--402, 1970.
• 6: Moses Charikar , Konstantin Makarychev , Yury Makarychev, Near-optimal algorithms for unique games, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132547]
• 7: Irit Dinur , Ehud Friedgut , Guy Kindler , Ryan O'Donnell, On the fourier tails of bounded functions over the discrete cube, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132580]
• 8: Z. Furedi. Random Polytopes in the d-Dimensional Cube. Discrete Comput. Geom., 1:315--319, 1986.
• 9: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 10: Venkatesan Guruswami , Daniel Lewin , Madhu Sudan , Luca Trevisan, A Tight Characterization of NP with 3 Query PCPs, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.8, November 08-11, 1998
• 11: G. Hast. Beating a Random Assignment -- Approximating Constraint Satisfaction Problems. PhD thesis, KTH -- Royal Institute of Technology, 2005.
• 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: Johan Håstad, Every 2-CSP allows nontrivial approximation, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060700]
• 14: Johan Håstad, On the Approximation Resistance of a Random Predicate, Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, August 20-22, 2007, Princeton, NJ, USA [doi>10.1007/978-3-540-74208-1_11]
• 15: S. Janson. Gaussian Hilbert Spaces. Cambridge University Press, 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: M. Kochol. Constructive approximation of a ball by polytopes. Math. Slovaca, 44(1):99--105, 1994.
• 18: E. Mossel. Gaussian bounds for noise correlation of functions. arXiv Report math/0703683v3, 2007.
• 19: 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]
• 20: 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]
• 21: Luca Trevisan, Approximation Algorithms for Unique Games, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.197-205, October 23-25, 2005 [doi>10.1109/SFCS.2005.22]
• 22: 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

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Theory

Keywords:
approximation resistance, k-wise independence