We propose that a novel deformation of string perturbation theory, involving non-local interactions between strings, is required to describe the gravity duals of field theories deformed by multiple-trace operators. The new perturbative expansion involves a new parameter, which is neither the string coupling nor the coefficient of a vertex operator on the worldsheet. We explore some of the properties of this deformation, focusing on a special case where the deformation in the field theory is exactly marginal.