The Integrability of the Square Exponential Transportation Cost

Let X1,.,Xn,Y1,.,Yn be i.i.d. with the uniform distribution on ([0,1]2,..), where .. denotes the Euclidean norm. Using a new presentation of the Ajtai-Komlos-Tusnady (AKT) transportation algorithm, it is shown that the square exponential transportation cost inf..ni=1exp(.Xi.Y.(i).K(logn/n)1/2)2, where . ranges over all permutations of the integers 1,.,n, satisfies an integrability condition. This condition strengthens the optimal matching results of AKT and supports a recent conjecture of Talagrand. Rates of growth for the Lp transportation cost are also found.