I Introduction1 Overview of the Thesis1.1 Motivation1.2 Problems Studied in This Thesis1.2.1 Constraint Satisfaction Problem (CSP)1.2.2 Computational Learning1.3 Organization and Summary1.3.1 Organization1.3.2 Summary of Thesis Contributions2 Background2.1 Notations2.2 Approximation and Hardness of Approximation2.3 CSPs and SDP 2.3.1 CSPs2.3.2 SDP Gap2.4 Learning Theory2.4.1 Concept Classes2.4.2 Learning Models2.4.3 Related Work 2.5 Label-Cover and Khot's Conjectures2.5.1 UGC v.s. d-to-1 Conjecture2.6 Dictator Testing2.6.1 Dictator Testing for CSPs2.6.2 Dictator Test for Learning3 Mathematical Tools3.1 Probability Theory3.1.1 Product Space3.1.2 Influence, Noise and Stability3.2 Advanced Probability Machineries3.2.1 Invariance Principle3.2.2 HypercontractivityII CSPs and SDP4 Approximation Curve for Max Cut4.1 Introduction4.1.1 Definitions4.1.2 SDP Gaps of Max Cut4.1.3 RPR2 Algorithms4.1.4 Dictator Tests of "="4.1.5 Motivation and Discussion4.1.6 Statement of Main Results4.1.7 The Critical Curve, S4.1.8 Prior Work4.1.9 Comparison with Raghavendra's Result4.2 Proof Overview4.2.1 Embedded Graphs4.2.2 Gaussian Mixture Graphs4.2.3 Hermite Analysis, Minimax, and Borell's Gaussian Rearrangement4.2.4 Organizations of the Remaining Proof4.3 GapSDP(c) S(c): Hermite Analysis and Borell's Rearrangement4.3.1 SDP Gaps via Gaussian Mixture graphs4.3.2 Proof of Theorem 4.3.34.3.3 Proof of Theorem 4.3.44.4 GapSDP(c) S(c): Discretized RPR2 and Minimax4.4.1 Discretizing Distributions4.4.2 Minimax4.4.3 More Minimax; Convexity and Concavity4.4.4 Undiscretizing4.5 Estimating S(c) Efficiently4.5.1 Evading Singularity4.6 On S(c) and Running Times4.6.1 On S(c)4.6.2 On the Running Time of the Rounding Algorithm4.7 Ddictator-vs.-quasirandom Tests4.8 GapTest(c) S(c): Invariance Principle4.8.1 Proof of Theorem 4.8.34.9 GapTest(c) S(c): RPR2 Algorithms Imply Testing Lower Bounds4.10 Hardness Results for RPR2 Algorithms4.11 GapSDP(c) is Continuous4.12 SDP Gaps Based on Infinite, Self-looped Graphs4.13 RPR2 Ď Implementation Issues4.14 Improved Asymptotics of S(12+ )4.15 Approximate Values of S(c)5 Conditional Hardness of Approximating Satisfiable 3-CSPs5.1 Introduction5.1.1 The PCP Characterization of NP5.1.2 Hardness of Approximation and Khot's Conjectures5.1.3 Satisfiable Max NTW5.2 Our Contribution and Methods5.2.1 Main Results5.2.2 Methods5.2.3 Related and Subsequent Work5.2.4 PCP System Framework5.3 The Test and the Analysis 5.3.1 Idea of Constructing Te5.3.2 Analysis of the Verifier5.4 Noise Operator5.5 Probability Space 5.6 Matrix Theory6 SDP gaps for variants of Label Cover6.1 Introduction6.1.1 Motivations6.1.2 Statements of the Conjectures6.1.3 Evidence for and against6.1.4 SDP gaps as a reduction tool6.2 Our Results6.3 Preliminaries and Notation6.3.1 2-to-1, 2-to-2 and Label-Cover Problems6.3.2 Fourier Analysis6.4 Integrality Gap for 2-to-2 Games6.4.1 SDP Solution6.4.2 Soundness6.5 Integrality Gap for 2-to-1 Label-Cover6.5.1 Gap Instance6.5.2 SDP Value6.5.3 Soundness6.6 From 2-to-1 Constraints to -constraints6.7 Discussion7 Unique Games over Integers7.1 Introduction7.1.1 Motivation7.1.2 Related Work7.1.3 Statement of Our Results7.2 Overview of Our Proof7.2.1 Comparison with GuruswamiĚRaghavendra7.3 Definitions and analytic tools7.3.1 Notation7.3.2 Noise stability and influences on [q]nRm 7.3.3 Hypercontractivity and Majority Is Stablest7.4 Dictator Tests7.4.1 Technical lemma7.4.2 Soundness of the test7.5 The Reduction from Unique-Games L7.5.1 Proof of Theorem 8.4.38 On Hardness of vertex pricing8.1 Introduction8.1.1 Motaviation and Background8.1.2 Problem definitions8.1.3 Main result8.2 Preliminaries8.2.1 Dictator Test for vertex pricing8.2.2 Mathematical tools8.3 Dictator Test for vertex pricing8.3.1 Description of the Dictator Test8.3.2 Analysis of the Dictator TestT8.4 The reduction from the Unique-Games8.4.1 Proof of Theorem 8.4.3III Hardness of Learning9 Hardness of Learning Monomials9.1 Introduction9.2 Proof Overview9.3 Preliminaries9.3.1 Critical Index9.3.2 Invariance Principle9.4 Construction of the Dictatorship Test9.4.1 Distributions D0 and D19.4.2 The Dictatorship Test9.4.3 Soundness Analysis9.5 Reduction from k-Unique Label-Cover9.6 Reduction from Label Cover9.6.1 Smooth k-Label-Cover9.6.2 Reduction from Smooth k-Label-Cover9.6.3 Proof of Theorem 9.1.19.6.4 Soundness Analysis9.7 Probabilistic Inequalities9.8 Proof of Lemma 9.3.3 9.9 Proof of Invariance Principle (Theorem 9.3.10)9.10 Hardness of Smooth k-Label-Cover10 Hardness of Learning Low degree PTFs10.1 Introduction10.1.1 Motivation10.1.2 Our Main results10.1.3 Overview of the Proof10.2 On Hardness of Proper Learning Degree d PTFs10.2.1 Dictator Test10.2.2 Hardness Reduction from Unique-Games10.2.3 Discretizing the Gaussian Distribution10.2.4 For d being Super-constant10.3 Hardness of Learning Halfspaces with degree 2 PTFs10.3.1 The Dictator Test10.3.2 Hardness Reduction from Label Cover10.4 Probability Inequalities10.5 Folding Lemma10.6 Discretization of the Gaussian distributionIV Open Problems11 Open ProblemsThe Approximability of Learning andConstraint Satisfaction ProblemsYi WuCMU-CS-10-142October 7, 2010School of Computer ScienceCarnegie Mellon UniversityPittsburgh, PA 15213Thesis Committee:Ryan O’Donnell, ChairAvrim BlumVenkatesan GuruswamiSubhash KhotSubmitted in partial fulfillment of the requirementsfor the degree of Doctor of Philosophy.Copyright © 2010 Yi WuThis research was sponsored by the National Science Foundation under grant numbers CCF-0747250, CCR-0122588; US Army Research Office under grant number DAAD-190210389; and generous support fromInternational Business Machine. The views and conclusions contained in this document are those of theauthor and should not be interpreted as representing the official policies, either expressed or implied, of anysponsoring institution, the U.S. government or any other entity.Keywords: Complexity Theory, Approximation Algorithm, Computational Learning,Constraint Satisfaction Problem, Hardness of Approximation, Semidefinite ProgrammingThis thesis is dedicated to my parents Youqun Yu, Qingchun Wu and my wife Xiaoxiao Li.4AbstractAnα-approximation algorithm is an algorithm guaranteed to output a solu-tion that is within anαratio of the optimal solution. We are interested in thefollowing question: Given an NP-hard optimization problem, what is the bestapproximation guarantee that any polynomial time algorithm could achieve?We mostly focus on studying the approximability