• Login
    • Submit
    View Item 
    •   Repository Home
    • UT Electronic Theses and Dissertations
    • UT Electronic Theses and Dissertations
    • View Item
    • Repository Home
    • UT Electronic Theses and Dissertations
    • UT Electronic Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Strong lower bounds on generic convex relaxations

    Icon
    View/Open
    KOTHARI-DISSERTATION-2016.pdf (1.473Mb)
    Date
    2016-08
    Author
    Kothari, Pravesh Kumar
    0000-0002-8689-6770
    Share
     Facebook
     Twitter
     LinkedIn
    Metadata
    Show full item record
    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.
    Department
    Computer Sciences
    Subject
    Lower bounds
    Semidefinite programming
    Planted clique
    Constraint satisfaction
    URI
    http://hdl.handle.net/2152/44040
    Collections
    • UT Electronic Theses and Dissertations
    University of Texas at Austin Libraries
    • facebook
    • twitter
    • instagram
    • youtube
    • CONTACT US
    • MAPS & DIRECTIONS
    • JOB OPPORTUNITIES
    • UT Austin Home
    • Emergency Information
    • Site Policies
    • Web Accessibility Policy
    • Web Privacy Policy
    • Adobe Reader
    Subscribe to our NewsletterGive to the Libraries

    © The University of Texas at Austin

    Browse

    Entire RepositoryCommunities & CollectionsDate IssuedAuthorsTitlesSubjectsDepartmentThis CollectionDate IssuedAuthorsTitlesSubjectsDepartment

    My Account

    Login

    Information

    AboutContactPoliciesGetting StartedGlossaryHelpFAQs

    Statistics

    View Usage Statistics
    University of Texas at Austin Libraries
    • facebook
    • twitter
    • instagram
    • youtube
    • CONTACT US
    • MAPS & DIRECTIONS
    • JOB OPPORTUNITIES
    • UT Austin Home
    • Emergency Information
    • Site Policies
    • Web Accessibility Policy
    • Web Privacy Policy
    • Adobe Reader
    Subscribe to our NewsletterGive to the Libraries

    © The University of Texas at Austin