Hardness of approximation results are composed of two main ingredients.
The first one is the determination of a good "starting point", that is
the proof that some, possibly artificial, problem is hard to approximate.
The celebrated results on Probabilistically Checkable Proofs (PCP) are
of this nature. In this talk we will describe some new PCP constructions
that improve previous ones with respect to several parameters. The second
ingredient is to show that the (known) hardness of approximation of a certain
problem implies the hardness of approximation of another problem of interest.
This process of showing that the hardness of a problem implies the hardness
of another problem is implemented by means of "approximation-preserving"
reductions. We will use this methodology to prove that the Traveling Salesman
Problem (TSP) is hard to approximate within some constant factor even for
Euclidean instances of logarithmic dimension. Arora's approximation algorithm
for Euclidean TSP works in time doubly-exponential in the number of dimensions
of the Euclidean space. Our result shows that such a terrible dependance
is in fact necessary.