English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We give some natural sufficient conditions for balls in a metric space tohave small intersection. Roughly speaking, this happens when the metric spaceis (i) expanding and (ii) well-spread, and (iii) a certain random variable onthe boundary of a ball has a small tail. As applications, we show that thevolume of intersection of balls in Hamming, Johnson spaces and symmetric groupsdecay exponentially as their centers drift apart. To verify condition (iii), weprove some large deviation inequalities `on a slice' for functions withLipschitz conditions.  We then use these estimates on intersection volumes to  $\bullet$ obtain a sharp lower bound on list-decodability of random $q$-arycodes, confirming a conjecture of Li and Wootters; and  $\bullet$ improve the classical bound of Levenshtein from 1971 on constantweight codes by a factor linear in dimension, resolving a problem raised byJiang and Vardy.  Our probabilistic point of view also offers a unified framework to obtainimprovements on other Gilbert--Varshamov type bounds, giving conceptuallysimple and calculation-free proofs for $q$-ary codes, permutation codes, andspherical codes. Another consequence is a counting result on the number ofcodes, showing ampleness of large codes.

Exponential decay of intersection volume with applications on list-decodability and Gilbert-Varshamov type bound