Oded Goldreich

We provide an exposition of three Lemmas which relate

general properties of distributions

with the exclusive-or of certain bit locations.

The first XOR-Lemma, commonly attributed to U.V. Vazirani,

relates the statistical distance of a distribution from uniform

to the maximum bias of the xor of certain bit positions.

more >>>

Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma

A binary code $\text{Enc}:\{0,1\}^k \rightarrow \{0,1\}^n$ is $(\frac{1}{2}-\varepsilon,L)$-list decodable if for every $w \in \{0,1\}^n$, there exists a set $\text{List}(w)$ of size at most $L$, containing all messages $m \in \{0,1\}^k$ such that the relative Hamming distance between $\text{Enc}(m)$ and $w$ is at most $\frac{1}{2}-\varepsilon$.

A $q$-query local list-decoder is ...
more >>>