We study the circuit complexity of the multiselection problem: given an input string x \in \{0,1\}^n along with indices i_1,\dots,i_q \in [n], output (x_{i_1},\dots,x_{i_q}). A trivial lower bound for the circuit size is the input length n + q \cdot \log(n), but the straightforward construction has size \Theta(q \cdot n).

... more >>>