The UGC Hardness Threshold of the L_p Grothendieck Problem

References

• Achlioptas D., Naor A., Peres Y. Rigorous location of phase transitions in hard optimization problems. Nature (2005) 435:759–764Crossref, Google Scholar
• Alon N., Berger E. The Grothendieck constant of random and pseudo-random graphs. Discrete Optim. (2008) 5(2):323–327Crossref, Google Scholar
• Alon N., Naor A. Approximating the cut-norm via Grothendieck's inequality. SIAM J. Comput. (2006) 35(4):787–803Crossref, Google Scholar
• Alon N., Makarychev K., Makarychev Y., Naor A. Quadratic forms on graphs. Inventiones Math. (2006) 163(3):499–522Crossref, Google Scholar
• Arora S., Berger E., Kindler G., Hazan E., Safra S. On non-approximability for quadratic programs. Proc. 46th Annual Sympos. Foundations Comput. Sci. (2005) (IEEE Computer Society)206–215Crossref, Google Scholar
• Artin E.The Gamma Function (1964) (Holt, Rinehart and Winston, New York) Athena Series: Selected Topics in Mathematics[Translated by Michael Butler]Google Scholar
• Bachas C. P. Computer-intractability of the frustration model of a spin glass. J. Phys. A: Math. General (1984) 17:709–712Crossref, Google Scholar
• Bansal N., Blum A., Chawla S. Correlation clustering. Machine Learning (2004) 56(1–3):89–113Crossref, Google Scholar
• Bansal N., Bravyi S., Terhal B. M. Classical approximation schemes for the ground-state energy of quantum and classical lsing spin Hamiltonians on planar graphs. Quantum Inform. Comput. (2009) 9(7 and 8):0701–0720Google Scholar
• Barahona F. On the computational complexity of Ising spin glass models. J. Phys. A: Math. General (1981) 15:3241–3253Crossref, Google Scholar
• Bellare M., Rogaway P. The complexity of approximating a nonlinear program. Math. Programming Ser. A (1995) 69(3):429–441Crossref, Google Scholar
• Ben Arous G., Dembo A., Guionnet A. Aging of spherical spin glasses. Probab. Theory Related Fields (2001) 120(1):1–67Crossref, Google Scholar
• Bieche L., Maynard R., Rammal R., Uhry J. P. On the ground states of the frustration model of a spin glass by a matching method of graph theory. J. Phys. A: Math. General (1980) 13:2553–2576Crossref, Google Scholar
• Brieden A. Geometric optimization problems likely not contained in 𝔸ℙ𝕏. Discrete Computational Geometry (2002) 28(2):201–209Crossref, Google Scholar
• Charikar M., Wirth A. Maximizing quadratic programs: Extending Grothendieck's inequality. Proc. 45th Annual Sympos. Foundations Comput. Sci. (2004) (IEEE Computer Society)54–60Crossref, Google Scholar
• Charikar M., Makarychev K., Makarychev Y. Near-optimal algorithms for unique games (extended abstract). Proc. 38th Annual ACM Sympos. Theory Comput. (2006) (ACM, New York) 205–214Google Scholar
• de Klerk E., Laurent M., Parrilo P. A. A PTAS for the minimization of polynomials of fixed degree over the simplex. Theoret. Comput. Sci. (2006) 361(2–3):210–225Crossref, Google Scholar
• Diestel J., Jarchow H., Tonge A.Absolutely Summing Operators, Cambridge Studies in Advanced Mathematics (1995) 43(Cambridge University Press, Cambridge, MA) Crossref, Google Scholar
• Feige U., Goemans M. Approximating the value of two proper proof systems with applications to MAX-2SAT and MAX-DICUT. Proc. Third Israel Sympos. Theory Comput. Systems (1995) (Institute of Electrical and Electronics Engineers, Washington, DC) 182–189Crossref, Google Scholar
• Feige U., Langberg M. The RPR2 rounding technique for semidefinite programs. J. Algorithms (2006) 60(1):1–23Crossref, Google Scholar
• Feige U., Lovász L. Two-prover one-round proof systems, their power and their problems. Proc. 24th Annual ACM Sympos. Theory Comput. (1992) (ACM, New York) 733–744Google Scholar
• Goemans M. X., Williamson D. P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. (1995) 42(6):1115–1145Crossref, Google Scholar
• Grötschel M., Lovász L., Schrijver A.Geometric Algorithms and Combinatorial Optimization, Vol.2. Algorithms and Combinatorics (1993) 2nd ed.(Springer-Verlag, Berlin) Crossref, Google Scholar
• Hall P. Rates of convergence in the central limit theorem. Research Notes in Mathematics (1982) 62(Pitman (Advanced Publishing Program), Boston) Google Scholar
• Halperin E., Hazan E. HAPLOFREQ—Estimating haplotype frequencies efficiently. J. Comput. Biol. (2006) 13(2):481–500Crossref, Google Scholar
• Johnson W. B., Lindenstrauss J. Basic concepts in the geometry of Banach spaces. Handbook of the Geometry of Banach Spaces (2001) I(North-Holland, Amsterdam) 1–84Crossref, Google Scholar
• Karger D., Motwani R., Sudan M. Approximate graph coloring by semidefinite programming. J. ACM (1998) 45(2):246–265Crossref, Google Scholar
• Khot S. On the power of unique 2-prover 1-round games. Proc. Thirty-Fourth Annual ACM Sympos. Theory Comput. (2002) (ACM, New York) 767–775 http://portal.acm.org/citation.cfm?id=510017Google Scholar
• Khot S., O'Donnell R. SDP gaps and UGC-hardness for MAXCUTGAIN. Proc. 47th Annual Sympos. Foundations Comput. Sci. (2006) (IEEE Computer Society)217–226Crossref, Google Scholar
• Machta J. The computational complexity of pattern formation. J. Statist. Phys. (1993) 70:949–966Crossref, Google Scholar
• Megretski A. Relaxations of quadratic programs in operator theory and system analysis. Systems, Approximation, Singular Integral Operators, and Related Topics (Bordeaux, 2000), Vol. 129. Operator Theory Advances and Applications. (2001) (Birkhäuser, Basel) 365–392Crossref, Google Scholar
• Nemirovski A., Roos C., Terlaky T. On maximization of quadratic form over intersection of ellipsoids with common center. Math. Program. Ser. A (1999) 86(3):463–473Crossref, Google Scholar
• Nesterov Y. Global quadratic optimization via conic relaxation. (1998) . Working paper, CORE. http://www.core.ucl.ac.be/services/psfiles/dp98/dp9860.pdfGoogle Scholar
• Sompolinsky H., Zippelius A. Dynamic theory of the spin-glass phase. Phys. Rev. Lett. (1981) 47(5):359–362Crossref, Google Scholar
• van Beek P. An application of Fourier methods to the problem of sharpening the Berry-Esseen inequality. Z. Wahrscheinlichkeitstheorie Verw. Gebiete (1972) 23:187–196Crossref, Google Scholar
• Wolfram S. Undecidability and intractability in theoretical physics. Phys. Rev. Lett. (1985) 54:735–738Crossref, Google Scholar