On extracting common random bits from correlated sources on large alphabets

Siu On Chan, Elchanan Mossel, Joe Neeman

Suppose Alice and Bob receive strings $X=(X_1,...,X_n)$ and $Y=(Y_1,...,Y_n)$ each uniformly random in $[s{]}^n$ but so that $X$ and $Y$ are correlated . For each symbol $i$, we have…