In this talk, I will provide a brief introduction to the area of hardness of approximation by proving an illustrative result.

In the Clique problem, we are given a graph $G$ and an integer $k$, and the goal is to find a complete subgraph on $k$ vertices in $G$. We will show that, assuming there is no $2^{o(n)}$-time algorithm that solves the Clique problem on $n$ vertices, there is no polynomial-time algorithm that can find a complete subgraph of size $k/2$ in $G$, even when the graph is promised to contain a complete subgraph of size $k$.

All details of the proof will be presented, and no background will be assumed.