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