# “long code test” and “dictatorship test”

Why is "long code test" also called "dictatorship test"?

I got really confused when I read about it in Arora's survey.

Let's start with the natural definition of the long code: The message is an $n$-bit string $i$ (the reason I'm calling this $i$ and not $x$ becomes clear soon) and the encoding is a vector $y$ of length $2^{2^n}$ where the positions of $y$ are indexed by all possible Boolean functions that map $n$ bits to one bit. Moreover, $y$ at position $f$ is simply $f(i)$.
Now you can alternatively identify $f$ by its truth table. So you can also assume that the coordinate positions of $y$ are indexed by all possible strings of length $N := 2^n$ (i.e., all possible truth tables) and then $y$ at position $f=(f_1, \ldots, f_N)$ just encodes $f_i$. So the $i$th codeword is the truth table of the $i$th dictator function (among the dictator functions mapping $N$ bits to one bit). So the long code and the dictator code are the same. In the long code interpretation, codewords correspond to $n$-bit points and codeword positions correspond to $n$-bit predicates. In the dictator code interpretation, codewords correspond to dictator functions on $2^n$ bits and codeword positions correspond to evaluation points.
Here's the explanation: If you want to encode a message $x\in \{0,1\}^n$ using the long code, you compute $f(x)$ for every function $f:\{0,1\}^n\to \{0,1\}$. Now think of each function $f$ as represented using the vector $v_f\in\{0,1\}^{2^n}$ that consists of the value of $f$ on each and every point $x\in\{0,1\}^n$. You can think of the long code codeword associated with $x$ as mapping the vector $v_f$ to position $x$ in $v_f$, i.e., as the dictator associated with position $x$.
(The dictator $D:\{0,1\}^N\to \{0,1\}$ associated with position $1\leq i\leq N$ is a function that maps $x\in\{0,1\}^N$ to $x_i$. It is "dictated" by the $i$'th position. Above, $N = 2^n$.)