A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. Barak, B., Hopkins, S. B., Kelner, J. A., Kothari, P. K., Moitra, A., & Potechin, A. SIAM J. Comput., 48(2):687–735, 2019. Special issue for FOCS 2016

Paper doi bibtex 9 downloads

@article{BarakHKKMP19,
  author    = {Boaz Barak and
               Samuel B. Hopkins and
               Jonathan A. Kelner and
               Pravesh K. Kothari and
               Ankur Moitra and
               Aaron Potechin},
  title     = {A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem},
  journal   = {{SIAM} J. Comput.},
  volume    = {48},
  number    = {2},
  pages     = {687--735},
  year      = {2019},
  doi       = {10.1137/17M1138236},
  timestamp = {Thu, 23 May 2019 17:55:00 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/siamcomp/BarakHKKMP19},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  url_paper = {http://eccc.hpi-web.de/report/2016/058/},
   selected = {yes},
  note = {Special issue for  FOCS 2016}
}

Downloads: 9