<p>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.</p>

<p>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$.</p>

<p>(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$.)</p>

CC BY-SA 3.0
2011-09-08T22:09:28.983Z
2011-09-08T22:09:28.983Z
Dana Moshkovitz
<p>"Long code" and "Dictator code" are two different names for the same code. Here's why:</p>

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

<p>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.</p>

CC BY-SA 3.0
2011-09-08T22:17:18.837Z
2011-09-08T22:17:18.837Z
Mahdi Cheraghchi
<p>Why is "long code test" also called "dictatorship test"? </p>

<p>I got really confused when I read about it in <a href="http://arxiv.org/abs/cs/0304038" rel="nofollow">Arora's survey</a>.</p>

<cc.complexity-theory><co.combinatorics><boolean-functions><coding-theory>
"long code test" and "dictatorship test"
j.s.
# "long code test" and "dictatorship test"

(Asked by: username_0 on 2011-09-08)

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

I got really confused when I read about it in [Arora's survey](http://arxiv.org/abs/cs/0304038).

**Tags:** cc.complexity-theory, co.combinatorics, boolean-functions, coding-theory

---

## 2 answers

### Answer by username_2 on 2011-09-08. Score: 11 | Accepted answer

"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.


---

### Answer by username_1 on 2011-09-08. Score: 10

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


---

