Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with association schemes:
TR13-105 | 29th July 2013
Raghu Meka, Avi Wigderson

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

Revisions: 1

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 = ... more >>>

ISSN 1433-8092 | Imprint