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

Our main result is an $O(n+q \cdot \log^3(n))$-size and $O(\log(n+q))$ depth circuit for multiselection. In particular, for any $q \leq n/\log^3(n)$ the circuit has linear size and logarithmic depth. Prior to our work no linear-size circuit for multiselection was known for any $q=\omega(1)$ and regardless of depth.