I didn't know about his inequalities, but I found (1) that provides an example of using Talagrand inequality applied to the longest increasing subsequence problem (12 pages, easy to read). It seems to be a broad generalization of the Hamming distance.
http://doc.9gridchan.info/blog/181230.ncubic.routing http://doc.9gridchan.info/blog/190104.ncubic.algorithms
Fromm mycrovtif (RIP), a guy from the plan9/9front community.