Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LINEAR-SIZE CIRCUITS:
Reports tagged with linear-size circuits:
TR23-113 | 8th August 2023
Justin Holmgren, Ron Rothblum

Linear-Size Boolean Circuits for Multiselection

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



ISSN 1433-8092 | Imprint