Strong lower bounds on generic convex relaxations

Abstract

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 << \sqrt{n} has been used as a starting point in many works. We show that algorithms with running time n^{o(log n)} based on the sum-of-squares method cannot detect planted cliques when \omega << \sqrt{n}. Sum-of-Squares method is a general scheme based on SDP that extends natural LP relaxations and spectral methods, captures the best approximation algorithms for fundamental problems and is the prime candidate for refuting the Unique Games Conjecture. Further, we show that any sub-exponential algorithm based on the sum-of-squares method cannot outperform simply returning an assignment at random for any pairwise independent CSP - a large class of CSPs not known be NP-hard to approximate beyond the random assignment threshold. Finally, we show that sub-exponential size (number of inequalities/constraints) LP that encodes MAX-CSP as a linear optimization over any fixed polytope are no more powerful than the well-known Sherali-Adams LP of similar size. This immediately yields a sub-exponential size lower bound for any LP that obtains >0.5 approximation for MaxCut showing an exponential separation between linear and semidefinite programming.