Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR23-113 | 8th August 2023 13:02

Linear-Size Boolean Circuits for Multiselection

RSS-Feed




TR23-113
Authors: Justin Holmgren, Ron Rothblum
Publication: 8th August 2023 14:51
Downloads: 391
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint