On the complexity of monotone circuits for threshold symmetric Boolean functions
From MaRDI portal
Publication:2064376
DOI10.1515/dma-2021-0031zbMath1484.94040OpenAlexW3207053979MaRDI QIDQ2064376
Publication date: 5 January 2022
Published in: Discrete Mathematics and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1515/dma-2021-0031
Switching theory, applications of Boolean algebras to circuits and networks (94C11) Boolean functions (94D10)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A 2.5 n lower bound on the monotone network complexity of \(T^ n_ 3\)
- New upper bounds on the Boolean circuit complexity of symmetric functions
- Sorting in \(c \log n\) parallel steps
- Extremal Combinatorics
- Bounds on Selection Networks
- Selection Networks
- On the combinational complexity of certain symmetric Boolean functions
- A Method of Constructing Selection Networks with $O(\log n)$ Depth
- A lower bound on CNF encodings of the at-most-one constraint