A widely studied question in theoretical computer science is whether one can compute approximate solutions to NP-hard problems efficiently and if not, whether one can prove that this task is computationally hard (the answer depends in general on specific problem at hand and the quality of approximation sought).

I will present some open problems from the hardness side, especially arising from the connections to combinatorics, analysis and geometry.