Hardness of Approximation - Part 1

Dive into the first part of a comprehensive tutorial on Hardness of Approximation presented by Ryan O'Donnell at the Metric 2011 workshop at IHP. Explore key concepts such as Max Cuts, Maximum Independent Set, Max K Cover, and the Unique Games Conjecture. Learn about basic decision problems, approximation algorithms, and the current state of affairs in the field. Gain insights into greedy algorithms, best-known approaches, and important approximability results. Engage with the material through questions and discussions, and familiarize yourself with essential notation and proofs in this 59-minute lecture, originally recorded by Nicolas Schabanel.

Introduction
Max Cuts On
Basic Decision
Maximum Independent Set
Max K Cover
Questions
Max Code
Key Definition
Approximation
Greedy algorithm
Best known algorithms
State of affairs
Unique games conjecture
Approximability results
Proof
Notation
More questions