Why is long code test also called dictatorship test? I got really confused when I read about it in Arora's survey.
long code test and dictatorship test
cc.complexity theory;co.combinatorics;boolean functions;coding theory
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.