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

Yash Deshpande Andrea Montanari

Published in: CoRR (2015)

Keyphrases

lower bound
data structure
branch and bound algorithm
randomly generated problems
neural network
learning algorithm
np hard
upper bound
worst case
np complete
decision problems
cutting plane
hidden information