# Course Identification

## Lecturers and Teaching Assistants

## Course Schedule and Location

## Field of Study, Course Type and Credit Points

## Comments

## Prerequisites

## Restrictions

## Language of Instruction

## Attendance and participation

## Grade Type

## Grade Breakdown (in %)

## Evaluation Type

**Seminar**

## Scheduled date 1

## Estimated Weekly Independent Workload (in hours)

## Syllabus

We will go over some recent progress in hardness of approximation, focusing on the unique games conjecture.

We will begin with the "label-cover long-code paradigm" of proving tight inapproximability results, describing Hastad's celebrated results for 3SAT, for linear equations, and for maximum clique.

We will then move to show implications of the unique games conjecture for hardness of approximation, for example for finding the maximum cut in a graph and for essentially every constraint satisfaction problem.

Then, we will proceed to read newer works that make progress on proving the unique games conjecture and the related 2:1 conjecture.

**The tentative list of topics is as follows:**

**Lecture 1:**

**1. Introduction: Constraint satisfaction problems, PCP theorem, Property testing**

**2. Basics: Boolean functions, Fourier analysis, Influence etc.**

**3. BLR Linearity Test**

**Lecture 2:**

**4. PCP Theorem implies gap3LIN(0.99, 1-\epsilon)**

**5. Parallel Repetition, Subcode covering, “linear” Label Cover instance**

**Lecture 3:**

**6. Hastad’s 3-bit PCP, Graph/Hypergraph Linearity Tests, amortized k-bit PCP**

**Lecture 4:**

**7. Majority is the Stablest Theorem, Invariance Principle**

**8. Unique Games Conjecture, Max-Cut algorithm and UG-hardness**

**Lecture 5:**

**9. (UGC + Hypergraph Linearity Test)**

**10. Chan’s Approximation resistance, Invariance Principle**

**Lecture 6:**

**11. FGLSS reduction, free bits, independent set**

**Lecture 7-8:**

**12. 2-to-1 conjecture, Grassmann graph, agreement hypothesis**

**13. 2-to-1 Theorem with imperfect completeness**

**Lecture 9:**

**14. Small set expansion hypothesis, Short Code.**

**Lecture 10:**

**15. Other hardness assumptions: Feige’s random 3SAT hypothesis, ETH, Planted Clique.**

## Learning Outcomes

The student will have understanding of the state of the art in hardness of approximation