Strong lower bounds on generic convex relaxations
Pravesh K. Kothari · Texas ScholarWorks (Texas Digital Library) · 2016
Despite significant successes in understanding the hardness of computational problems based on standard assumptions such as P != NP, there are important settings where the gap between what the best known algorithms achieve and what the best known hardness reductions can rule out is rather stark. This thesis aims at decreasing this gap by proving unconditional lower bounds on powerful algorithmic techniques based on linear (LP) and semi-definite programming (SDP) for Planted Clique and Constraint Satisfaction problems (CSPs). Planted Clique is a central question in average case complexity where the goal is to find a clique of size [omega] planted in the Erdős-Rényi random graph G(n,0.5). While information theoretically, such a clique can be found whenever [omega] >> 2log(n), state-of-the-art polynomial time algorithms succeed only when \\omega ~ \\sqrt{n}. In fact, the conjectured hardness of detecting planted cliques for \\omega 0.5 approximation for MaxCut showing an exponential separation between linear and semidefinite programming.