### Abstract

We prove that with high probability over the choice of a random graph G from the Erds-Rényi distribution G(n,1/2), the no(d)-time degree d Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least n1/2-c(d/log n)1/2 for some constant c > 0. This yields a nearly tight n1/2-o(1)) bound on the value of this program for any degree d = o(log n). Moreover we introduce a new framework that we call pseudo-calibration to construct Sum-of-Squares lower bounds. This framework is inspired by taking a computational analogue of Bayesian probability theory. It yields a general recipe for constructing good pseudo-distributions (i.e., dual certificates for the Sum-of-Squares semidefinite program), and sheds further light on the ways in which this hierarchy differs from others.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 |

Publisher | IEEE Computer Society |

Pages | 428-437 |

Number of pages | 10 |

ISBN (Electronic) | 9781509039333 |

DOIs | |

State | Published - Dec 14 2016 |

Event | 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 - New Brunswick, United States Duration: Oct 9 2016 → Oct 11 2016 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

Volume | 2016-December |

ISSN (Print) | 0272-5428 |

### Other

Other | 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 |
---|---|

Country | United States |

City | New Brunswick |

Period | 10/9/16 → 10/11/16 |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)

### Keywords

- Algorithm design and analysis
- Computational complexity
- Mathematical programming

## Fingerprint Dive into the research topics of 'A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem'. Together they form a unique fingerprint.

## Cite this

*Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016*(pp. 428-437). [7782957] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2016-December). IEEE Computer Society. https://doi.org/10.1109/FOCS.2016.53