According to the so-called AdS/CFT correspondence,
many interesting 4D gauge theories possess an equivalent
description through closed strings. In order for this duality
to work, however, the strings must propagate in novel 5D
``holographic'' backgrounds. After reviewing key ideas and
features of gauge-string dualities, I shall extract a list of
new challenges that are posed to perturbative string theory.
Their formulation highlights interesting links with a variety
of current problems in mathematical physics, disordered electron
systems and surface critical phenomena. The talks concludes
with some promising recent developments that are being persued
to construct string theory in holographic backgrounds.
