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

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

up vote 10 down vote accepted

"Long code" and "Dictator code" are two different names for the same code. Here's why:

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.

This is because the "long code" is the same as the code of all "dictators". I'll explain how to see it below; it's not immediate. Once you verified it for yourself, you should just remember that it's two different ways to look at the same thing.

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$.)

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.