Strong lower bounds on generic convex relaxations

dc.contributor.advisorKlivans, Adam R.
dc.contributor.committeeMemberBarak, Boaz
dc.contributor.committeeMemberZuckerman, David
dc.contributor.committeeMemberRavikumar, Pradeep
dc.contributor.committeeMemberPrice, Eric
dc.creatorKothari, Pravesh Kumar
dc.creator.orcid0000-0002-8689-6770 2016
dc.description.abstractDespite 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.
dc.description.departmentComputer Sciences
dc.subjectLower bounds
dc.subjectSemidefinite programming
dc.subjectPlanted clique
dc.subjectConstraint satisfaction
dc.titleStrong lower bounds on generic convex relaxations
dc.type.materialtext Sciences science University of Texas at Austin of Philosophy

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
1.47 MB
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
1.84 KB
Plain Text