The UGC hardness threshold of the ℓp Grothendieck problem

ABSTRACT

For p ≥ 2 we consider the problem of, given an n × n matrix A = (a_ij) whose diagonal entries vanish, approximating in polynomial time the number {display equation} (where optimization is taken over real numbers).

When p = 2 this is simply the problem of computing the maximum eigenvalue of A, while for p = ∞ (actually it suffices to take p ≈ log n) it is the Grothendieck problem on the complete graph, which was shown to have a O(log n) approximation algorithm in [27, 26, 15], and was used in [15] to design the best known algorithm for the problem of computing the maximum correlation in Correlation Clustering. Thus the problem of approximating Opt_p (A) interpolates between the spectral (p = 2) case and the Correlation Clustering (p = ∞) case. From a physics point of view this problem corresponds to computing the ground states of spin glasses in a hard-wall potential well.

We design a polynomial time algorithm which, given p ≥ 2 and an n x n matrix A = (a_ij) with zeros on the diagonal, computes Opt_p (A) up to a factor p/e + 30 log p. On the other hand, assuming the unique games conjecture (UGC) we show that it is NP-hard to approximate (1.2) up to a factor smaller than p/e + 1/4. Hence as p → ∞ the UGC-hardness threshold for computing Opt_p (A) is exactly p/e (1 + o(1)).

REFERENCES

• 1: D. Achlioptas, A. Naor, and Y. Peres. Rigorous location of phase transitions in hard optimization problems. Nature, 435:759--764, 2005.
• 2: A. Alon and E. Berger. The Grothendieck constant of random and pseudo-random graphs. To appear in Discrete Optimization.
• 3: N. Alon, K. Makarychev, Y. Makarychev, and A. Naor. Quadratic forms on graphs. Invent. Math., 163(3):499--522, 2006.
• 4: Noga Alon , Assaf Naor, Approximating the Cut-Norm via Grothendieck's Inequality, SIAM Journal on Computing, v.35 n.4, p.787-803, 2006 [doi>10.1137/S0097539704441629]
• 5: Sanjeev Arora , Eli Berger , Guy Kindler , Muli Safra , Elad Hazan, On Non-Approximability for Quadratic Programs, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.206-215, October 23-25, 2005 [doi>10.1109/SFCS.2005.57]
• 6: E. Artin. The gamma function. Translated by Michael Butler. Athena Series: Selected Topics in Mathematics. Holt, Rinehart and Winston, New York, 1964.
• 7: C. P. Bachas. Computer-intractability of the frustration model of a spin glass. J. Phys. A: Math. Gen., 17:709--712, 1984.
• 8: N. Bansal, S. Bravyi, and B. M. Terhal. A classical approximation scheme for the ground-state energy of Ising spin Hamiltonians on planar graphs. Preprint, 2007.
• 9: F. Barahona. On the computational complexity of Ising spin glass models. J. Phys. A: Math. Gen., 15:3241--3253, 1981.
• 10: Mihir Bellare , Phillip Rogaway, The complexity of approximating a nonlinear program, Mathematical Programming: Series A and B, v.69 n.3, p.429-441, Sept. 28, 1995 [doi>10.1007/BF01585569]
• 11: G. Ben Arous, A. Dembo, and A. Guionnet. Aging of spherical spin glasses. Probab. Theory Related Fields, 120(1):1--67, 2001.
• 12: L. Bieche, R. Maynard, R. Rammal, and J. P. Uhry. On the ground states of the frustration model of a spin glass by a matching method of graph theory. J. Phys. A: Math. Gen., 13:2553--2576, 1980.
• 13: A. Brieden. Geometric optimization problems likely not contained in APX. Discrete Comput. Geom., 28(2):201--209, 2002.
• 14: 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]
• 15: Moses Charikar , Anthony Wirth, Maximizing Quadratic Programs: Extending Grothendieck's Inequality, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.54-60, October 17-19, 2004 [doi>10.1109/FOCS.2004.39]
• 16: Etienne de Klerk , Monique Laurent , Pablo A. Parrilo, A PTAS for the minimization of polynomials of fixed degree over the simplex, Theoretical Computer Science, v.361 n.2, p.210-225, 1 September 2006 [doi>10.1016/j.tcs.2006.05.011]
• 17: Uriel Feige , László Lovász, Two-prover one-round proof systems: their power and their problems (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.733-744, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129783]
• 18: M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin, second edition, 1993.
• 19: P. Hall. Rates of convergence in the central limit theorem, volume 62 of Research Notes in Mathematics. Pitman (Advanced Publishing Program), Boston, Mass., 1982.
• 20: E. Halperin and E. Hazan. HAPLOFREQ---estimating haplotype frequencies efficiently. J. Comput. Biol., 13(2):481--500 (electronic), 2006.
• 21: W. B. Johnson and J. Lindenstrauss. Basic concepts in the geometry of Banach spaces. In Handbook of the geometry of Banach spaces, Vol. I, pages 1--84. North-Holland, Amsterdam, 2001.
• 22: 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]
• 23: 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]
• 24: J. Machta. The computational complexity of pattern formation. J. Stat. Phys., 70:949--966, 1993.
• 25: A. Megretski. Relaxation of quadratic programs in operator theory and system analysis. Systems, Approximation, Singular Integral Operators, and Related Topics (Bordeaux, 2000), (3):365--392, 2001.
• 26: A. Megretski. Relaxations of quadratic programs in operator theory and system analysis. In Systems, approximation, singular integral operators, and related topics (Bordeaux, 2000), volume 129 of Oper. Theory Adv. Appl., pages 365--392. Birkhäuser, Basel, 2001.
• 27: A. Nemirovski, C. Roos, and T. Terlaky. On maximization of quadratic form over intersection of ellipsoids with common center. Math. Program., 86(3, Ser. A):463--473, 1999.
• 28: A. Nemirovski, C. Roos, and T. Terlaky. On maximization of quadratic form over intersection of ellipsoids with common center. Mathematical Programming, 86(3):463--473, 1999.
• 29: Y. Nesterov. Global quadratic optimization via conic relaxation. Working paper CORE, 1998.
• 30: H. Sompolinsky and A. Zippelius. Dynamic theory of the spin-glass phase. Phys. Rev. Lett., 47(5):359--362, 1981.
• 31: T. S. Motzkin and E. Straus. Maxima for graphs and a new proof of a theorem of turan. Canadian Journal of Mathematics, 17:533--540, 1965.
• 32: P. van Beek. An application of Fourier methods to the problem of sharpening the Berry-Esseen inequality. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 23:187--196, 1972.
• 33: S. Wolfram. Undecidability and intractability in theoretical physics. Phys. Rev. Lett., 54:735--738, 1985.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Design, Theory