Explore the Unique Games Conjecture and implications for optimization problems. Learn about subexponential algorithms, UGC barrier examples, and time vs. approximation trade-offs in solving unique games instances efficiently.
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Subexponential Algorithms for Unique Games and Related Problems Sanjeev Arora Princeton University & CCI Boaz Barak MSR New England David Steurer MSR New England U Approximation Algorithms, June 2011
Subexponential Algorithms for Unique Games and Related Problems Sanjeev Arora Princeton University & CCI Boaz Barak MSR New England David Steurer MSR New England Rounding Semidefinite Programming Hierarchies via Global Correlation Boaz Barak MSR New England Prasad Raghavendra Georgia Tech David Steurer MSR New England
? ? ?? ?? UNIQUE GAMES list of constraints of form ?? ??= ? mod ? Input: Goal: satisfy as many constraints as possible
UNIQUE GAMES list of constraints of form ?? ??= ? mod ? Input: Goal: satisfy as many constraints as possible Unique Games Conjecture (UGC) [Khot 02] For every ? > 0, the following is NP-hard: UNIQUE GAMESinstance with ? = log? (say) Input: Goal: Distinguish two cases UG(?) YES: more than 1 ? of constraints satisfiable NO: less than ? of constraints satisfiable
Implications of UGC For many basic optimization problems, it is NP-hard to beat current algorithms (based on simple LP or SDP relaxations) Examples: VERTEX COVER[Khot-Regev 03], MAX CUT[Khot-Kindler-Mossel-O Donnell 04, Mossel-O Donnell-Oleszkiewicz 05], every MAX CSP[Raghavendra 08],
Implications of UGC For many basic optimization problems, it is NP-hard to beat current algorithms (based on simple LP or SDP relaxations) Unique Games Barrier Example:(?GW+?)-approximation for MAX CUT at least as hard as UG(? ) ?GW= 0.878 Goemans Williamson bound for MAX CUT UNIQUE GAMES is common barrier for improving current algorithms of many basic problems
Subexponential Algorithm for Unique Games UG(?) in time exp ?? 1 3 Time vs Approximation Trade-off Input: Output: assignment satisfying 1 ? ? of constraints exp ? ? UNIQUE GAMES instance with alphabet size k such that 1 ? of constraints are satisfiable, 1 ? 2 3 Time:
Subexponential Algorithm for Unique Games UG ? in time exp ?? 1 3 Consequences 1 ? 1 3 (*) NP-hardness reduction for UG ? must have blow-up ? rules out certain classes of reductions for proving UGC Analog of UGC with subconstant ? (say ? = (contrast: subconstant hardness for LABEL COVER [Moshkovitz-Raz 08]) 1 loglog?) is false (*) UGC-based hardness does not rule out subexponential algorithms, Possibility:exp ??-time algorithm for MAX CUT(?GW+ ?) ? (*) assuming 3-SAT does not have subexponential algorithms, exp ?? 1
Subexponential Algorithm for Unique Games UG ? in time exp ?? 1 3 [Moshkovitz-Raz 08 + H stad 97] MAX CUT(?GW+ ?)? UG ? 78) 78+ ?) MAX 3-SAT( MAX CUT(???) MAX 3-SAT( LABEL COVER(?) FACTORING GRAPH ISOMORPHISM 2-SAT 3-SAT (*) exp ?? 1 3 exp(? exp(? 1 3) 1 2) poly ? exp(?) (*) assuming Exponential Time Hypothesis [Impagliazzo-Paturi-Zane 01] (3-SAT has no 2?(?) algorithm )
UNIQUE GAMES list of constraints of form ?? ??= ? mod ? Input: Goal: satisfy as many constraints as possible What we want: ?1, ,?? jointly distributed random variables over [?] for typical constraint ?? ?? ? Pr ?? ?? ? 1 ?
? distributions ?? over ?? for all ? with ? ? consistency ? ? ? same marginal for ? ? in distributions ?? and ?? positive semidefiniteness ??? = indicator of {??= ?} time ?? ? Cov(???,??? ??= ?) p.s.d. for all ? with ? ?-2 ?-level SDP hierarchy: What we want: ?-local jointly distributed random variables over [?] ?1, ,?? for typical constraint ?? ?? ? Pr ?? ?? ? 1 ? Goal: produce global random variables ? 1, ,? ? ? ?,? ? ??,?? for most constraints ?? ?? ? Here: iterative procedure for ? = ?? ?1/3 [Arora-Barak-S. 10 + Barak-Raghavendra-S. 11]
Components of iterative procedure Rounding sample variables independently according to their marginals Conditioning enough if constraint graph has few significant eigenvalues pick a vertex j and sample ?? condition ?1, ,?? on sample for ?? [BRS 11] Partitioning general framework for rounding SDP hierarchies find vertex subset ? break dependence between ?? and ?? ?
Rounding Conditioning Partitioning statistical distance between {??,??} and ??{??} max ? Cov ???,?? ?+? ? (Pairwise) Correlation decrease in variance when conditioning on ?? Corr(??,??) ??? ??? ??? ?????) ? similar to mutual information ? ?;? = ? ? ? ? ? Important fact: can approximate Corr(??,??) by Gram matrix of unit vectors (tensoring trick)
Rounding Conditioning Partitioning sample variables independently according to their marginals Corr(??,??) statistical distance between independent and correlated sampling If Corr ??,?? < 1 ?(?) then independent sampling satisfies constraint with probability (?) Rounding fails ?? ?Corr ??,?? > 1 ?(?) Local Correlation (over edges of constraint graph)
Rounding Conditioning Partitioning pick a vertex ? and sample ?? condition ?1, ,?? on sample for ?? Issue: computationally expensive (level ? level ? 1) Corr ??,?? measures decrease in variance when conditioning on ?? Idea: condition on vertex ? only if ??Corr ??,?? > ? ? can condition ?? times on such vertices Conditioning fails ??,?Corr ??,?? < ? ? Global Correlation (over random vertex pairs)
Rounding Conditioning Partitioning find vertex subset ? break dependence between ?? and ?? ? Issue: destroy correlation for constraints between ? and ? ? Wanted: set ? with small expansion & small cardinality ? ? ?
Rounding Conditioning Partitioning fails only if local correlation high ?? ?Corr ??,?? > 1 ?(?) fails only if global correlation low ??,?Corr ??,?? < ? ? ? ? find vertex subset ? ? break dependence between ?? and ?? ? Correlation Propagation ? For endpoints of random path of length ? = ( ? log?) ? ? ? ?? ??Corr ??,?? > 1 ? ? Corr ??,?? is Gram matrix of unit vectors random walk stuck for ? steps on ? ? fraction of vertices log ? ? vertex set ? with ? < ? /?? and expansion < ?/? A vertex is cut in at most 1/? partitioning steps break only ?/?3 edges
More SDP-hierarchy algorithms For general 2-CSP: [Barak-Raghavendra-S. 11] PTAS if constraint graph is random (degree alphabet) QPTAS if constraint graph is hypercontractive very good expander for small sets Subsequent work: [Arora-Ge 11] better 3-COLORING approximation on some graph families Independent work: [Guruswami-Sinop 11] approximation schemes for quadratic integer programming with p.s.d. objective & few relevant eigenvalues
Open Questions What else can be done in subexponential time? Better approximations for MAX CUTor VERTEX COVERon general instances? Example:?(?)-approximation for SPARSEST CUTin time exp(??)? Towards settling the Unique Games Conjecture How many large eigenvalues can a small-set expander have? Is Boolean noise graph the worst case? (polylog(?) large eigenvalues) No: small set expander with 2(log ?) (1) large eigenvalues [Barak-Gopalan-H stad-Meka-Raghavendra-S. 11] Thank you! Questions?
