A simple fourier analytic proof of the AKT optimal matching theorem

Sergey G. Bobkov, Michel Ledoux

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


We present a short and elementary proof of the Ajtai–Komlós–Tusnády (AKT) optimal matching theorem in dimension 2 via Fourier analysis and a smoothing argument. The upper bound applies to more general families of samples, including dependent variables, of interest in the study of rates of convergence for empirical measures. Following the recent pde approach by L. Ambrosio, F. Stra and D. Trevisan, we also adapt a simple proof of the lower bound.

Original languageEnglish (US)
Pages (from-to)2567-2584
Number of pages18
JournalAnnals of Applied Probability
Issue number6
StatePublished - Dec 2021

Bibliographical note

Funding Information:
Research of S.B. was partially supported by NSF Grant DMS-1855575.

Publisher Copyright:
© Institute of Mathematical Statistics, 2021


  • Ajtai–Komlós–Tusnády theorem
  • Empirical measure
  • Fourier analysis
  • Heat kernel smoothing
  • Optimal matching


Dive into the research topics of 'A simple fourier analytic proof of the AKT optimal matching theorem'. Together they form a unique fingerprint.

Cite this