Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-105 | 12th November 2013 17:53

Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique

RSS-Feed




Revision #1
Authors: Raghu Meka, Avi Wigderson
Accepted on: 12th November 2013 17:53
Downloads: 602
Keywords: 


Abstract:

Paper is withdrawn due to an error. In the previously uploaded manuscript, the error was in Theorem 1.6 which is not correct. We thank Gilles Pisier for pointing this out.


Paper:

TR13-105 | 29th July 2013 17:31

Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique





TR13-105
Authors: Raghu Meka, Avi Wigderson
Publication: 30th July 2013 19:27
Downloads: 1534
Keywords: 


Abstract:

Finding cliques in random graphs and the closely related ``planted'' clique variant, where a clique of size t is planted in a random G(n,1/2) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known polynomial-time algorithms only solve the problem for t = Theta(sqrt(n)). Here we show that beating sqrt(n) would require substantially new algorithmic ideas, by proving a lower bound for the problem in the sum-of-squares (or Lasserre) hierarchy, the most powerful class of semi-definite programming algorithms we know of: r rounds of the sum-of-squares hierarchy can only solve the planted clique for t > sqrt(n)/(C log n)^(r^2). Previously, no nontrivial lower bounds were known. Our proof is formulated as a degree lower bound in the Positivstellensatz algebraic proof system, which is equivalent to the sum-of-squares hierarchy.

The heart of our (average-case) lower bound is a proof that a certain random matrix derived from the input graph is (with high probability) positive semidefinite. Two ingredients play an important role in this proof. The first is the classical theory of association schemes, applied to the average and variance of that random matrix. The second is a new large deviation inequality for matrix-valued polynomials. Our new tail estimate seems to be of independent interest and may find other applications, as it generalizes both the estimates on real-valued polynomials and on sums of independent random matrices.



ISSN 1433-8092 | Imprint