O'Reilly logo

Concentration of Measure for the Analysis of Randomized Algorithms by Alessandro Panconesi, Devdatt P. Dubhashi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

13

Quadratic Transportation Cost and Talagrand’s Inequality

13.1 Introduction

In this chapter, we prove Talagrand’s convex distance inequality via the transportation cost method, an approach pioneered by Kati Marton [62] and further developed by Amir Dembo [25]. This approach is particularly interesting because:

• It places both the theorem and its proof in its natural place within the context of isoperimetric inequalities.

• It places a standard structure on the proof as opposed to the somewhat ad hoc nature of the original inductive proof of Talagrand.

• It isolates very clearly the essential content of the proof in one dimension and shows that the extension to higher dimensions is routine.

• It also allows a stronger version of the method ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required