Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems.

Yash Deshpande Andrea Montanari

Published in: COLT (2015)

Keyphrases

lower bound
upper bound
objective function
optimization problems
decision problems
branch and bound algorithm
hidden information
linear programming
branch and bound
problems involving
solving problems
randomly generated problems