## Abstract

We prove that with high probability over the choice of a random graph G from the Erd\H os-Rényi distribution G(n, 1/2), the n^{O}(d^{)}-time degree d sum-of-squares (SOS) semidefinite programming relaxation for the clique problem will give a value of at least n^{1}/2 - c(d/ log n^{)1}/^{2} for some constant c > 0. This yields a nearly tight n^{1}/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 pseudocalibration to construct SOS lower bounds. This framework is inspired by taking a computational analogue of Bayesian probability theory. It yields a general recipe for constructing good pseudodistributions (i.e., dual certificates for the SOS semidefinite program) and sheds further light on the ways in which this hierarchy differs from others.

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

Pages (from-to) | 687-735 |

Number of pages | 49 |

Journal | SIAM Journal on Computing |

Volume | 48 |

Issue number | 2 |

DOIs | |

State | Published - 2019 |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- General Mathematics

## Keywords

- Lower bound
- Planted clique
- Sum-of-squares