This post will cover some cool results in coding theory I’ve learned from Vadhan’s survey on pseudorandomness, with a focus on list-decoding algorithms and the tradeoff between rate and distance and culminating in a discussion of the folded Reed-Solomon code and its relationship to the Parvaresh-Vardy code.

We begin with some basic definitions.

**Definition 1**: For alphabet of size and block length , a **q-ary code **is a multiset inside the set of -words . The members of are called **codewords**.

**Definition 2**: An **encoding function** for a code is a bijection from the **messages** to the set of codewords, thought of as a labeling.

The set of -words from the alphabet has an obvious structure as a metric space, and this notion of distance will help us in developing a model of decoding.

**Definition 3**: The relative **Hamming distance ** for is the fraction of positions such that . Under this metric, denote to be the open ball of -words centered at with radius . This happens to be called the Hamming ball of radius around .

With these in mind, we will focus not on unique decoding, but on decoding algorithms that output *lists* of potential candidates and allow for handling of bigger batches of errors.

**Definition 4**: Let denote the set of codewords lying inside the Hamming ball of radius centered about . An encoding is said to be **-list-decodable **if for all -words .