Fetching the paper…
Reading the bibliography…
The problem of finding large cliques in random graphs and its "planted" variant, where one wants to recover a clique of size $\omega \gg \log{(n)}$ added to an \Erdos-\Renyi graph $G \sim G(n,\frac{1}{2})$, have been intensely studied.
Richard M. Karp, Probabilistic analysis of some combinatorial search problems , Algorithms and Complexity: New Directions and Recent Results (1976)
1976
Earlier work this paper cites.
Eiichi Bannai and Tatsuro Ito, Algebraic combinatorics. I , The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1984, Association schemes. MR 882540 (87m:05001)
1984
Earlier work this paper cites.
Andrzej Ruciński, When are small subgraphs of a random graph normally distributed? , Probability Theory and Related Fields 78
1988
Earlier work this paper cites.
Mark Jerrum, Large cliques elude the metropolis process , Random Struct. Algorithms 3
1992
Earlier work this paper cites.
Michel X Goemans and David P Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming , Journal of the ACM (JACM) 42
1995
Earlier work this paper cites.
Ludek Kucera, Expected complexity of graph partitioning problems , Discrete Applied Mathematics 57
1995
Earlier work this paper cites.
Noga Alon, Michael Krivelevich, and Benny Sudakov, Finding a large hidden clique in a random graph , SODA, 1998, pp. 594–598
1998
Earlier work this paper cites.
Uriel Feige and Robert Krauthgamer, Finding and certifying a large hidden clique in a semirandom graph , Random Struct. Algorithms 16
2000
Earlier work this paper cites.
Pablo A Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization , Ph.D. thesis, Citeseer, 2000
2000
Earlier work this paper cites.
Combinatorial approaches to finding subtle signals in dna sequences. , vol. 8, 2000
2000
Earlier work this paper cites.
Dima Grigoriev, Complexity of positivstellensatz proofs for the knapsack , Computational Complexity 10
2001
Earlier work this paper cites.
Dima Grigoriev, Linear lower bound on degrees of positivstellensatz calculus proofs for the parity , Theor. Comput. Sci. 259
2001
Earlier work this paper cites.
Jean B Lasserre, Global optimization with polynomials and the problem of moments , SIAM Journal on Optimization 11
2001
Earlier work this paper cites.
2001
Earlier work this paper cites.
Sanjeev Arora, Satish Rao, and Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning , Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, ACM, 2004, pp. 222–231
2004
Earlier work this paper cites.
Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning Xie, Testing k-wise and almost k-wise independence , STOC, 2007, pp. 496–505
2007
Earlier work this paper cites.
Alan M. Frieze and Ravi Kannan, A new approach to the planted clique problem , IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008, December 9-11, 2008, Bangalore, India, 2008, pp. 187–198
2008
Cited alongside, same era.
Grant Schoenebeck, Linear level lasserre lower bounds for certain k-csps , 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, 2008, pp. 593–602
2008
Cited alongside, same era.
S. Charles Brubaker and Santosh Vempala, Random tensors and planted cliques , Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings, 2009, pp. 406–419
2009
Cited alongside, same era.
How hard is it to approximate the best nash equilibrium? , 2009
2009
Cited alongside, same era.
Anindya De, Elchanan Mossel, and Joe Neeman, Majority is stablest: Discrete and sos , Proceedings of the forty-fifth annual ACM symposium on Theory of computing, ACM, 2013, pp. 477–486
2013
Later among the works it cites.
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, and Ying Xiao, Statistical algorithms and a lower bound for detecting planted cliques , Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, 2013, pp. 655–664
2013
Later among the works it cites.
Ryan O’Donnell and Yuan Zhou, Approximability and proof complexity , Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2013, pp. 1537–1556
2013
Later among the works it cites.
Boaz Barak, Sum of squares upper bounds, lower bounds, and open questions , Lecture Notes (2014), http://www.boazbarak.org/sos/files/all–notes.pdf
2014
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Madhur Tulsiani, CSP gaps and reductions in the lasserre hierarchy , Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, 2009, pp. 303–312
2009
Cited alongside, same era.
Sanjeev Arora, Boaz Barak, and David Steurer, Subexponential algorithms for unique games and related problems , Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, IEEE, 2010, pp. 563–572
2010
Cited alongside, same era.
Benny Applebaum, Boaz Barak, and Avi Wigderson, Public-key cryptography from different assumptions , STOC, 2010, pp. 171–180
2010
Cited alongside, same era.
Computational complexity and information asymmetry in financial products (extended abstract) , 2010
2010
Cited alongside, same era.
Per Austrin, Mark Braverman, and Eden Chlamtac, Inapproximability of np-complete variants of nash equilibrium , Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings, 2011, pp. 13–25
2011
Cited alongside, same era.
Boaz Barak, Prasad Raghavendra, and David Steurer, Rounding semidefinite programming hierarchies via global correlation , Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, IEEE, 2011, pp. 472–481
2011
Cited alongside, same era.
Svante Janson, Tomasz Luczak, and Andrzej Rucinski, Random graphs , vol. 45, John Wiley & Sons, 2011
2011
Cited alongside, same era.
Boaz Barak, Fernando GSL Brandao, Aram W Harrow, Jonathan Kelner, David Steurer, and Yuan Zhou, Hypercontractivity, sum-of-squares proofs, and their applications , Proceedings of the forty-fourth annual ACM symposium on Theory of computing, ACM, 2012, pp. 307–326
2012
Cited alongside, same era.
Boaz Barak, Jonathan A Kelner, and David Steurer, Rounding sum-of-squares relaxations , Proceedings of the 46th Annual ACM Symposium on Theory of Computing, ACM, 2014, pp. 31–40
2014
Later among the works it cites.
2014
Later among the works it cites.
2014
Later among the works it cites.
Boaz Barak, Siu On Chan, and Pravesh K. Kothari, Sum of squares lower bounds from pairwise independence , Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, 2015, pp. 97–106
2015
Closest in time.
Boaz Barak and Ankur Moitra, Tensor prediction, rademacher complexity and random 3-XOR , 2015
2015
Closest in time.
Yash Deshpande and Andrea Montanari, Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems , COLT (2015)
2015
Closest in time.
2015
Closest in time.
Samuel B. Hopkins, Jonathan Shi, and David Steurer, Tensor principle component analysis via sum of squares proofs , In Proc. COLT (2015)
2015
Closest in time.
James R Lee, Prasad Raghavendra, and David Steurer, Lower bounds on the size of semidefinite programming relaxations , Proceedings of the forty-seventh annual ACM symposium on Theory of computing, ACM, 2015
2015
Closest in time.
Sum-of-squares lower bounds for planted clique , 2015
2015
Closest in time.
Tengyu Ma and Avi Wigderson, Sum of squares lower bounds for sparse pca , Preprint (2015)
2015
Closest in time.
Prasad Raghavendra and Tselil Schramm, Tight lower bounds for planted clique in the degree-4 sos program , Preprint (2015)
2015
Closest in time.