Bounds on the Activity of Boolean Circuits Implementing Boolean Operators
Received: 26 Oct 2026 Accepted: 27 Oct 2026
Published: 2026, vol. 30, issue 4, pp. 164–167
Abstract
We consider two activity measures for Boolean circuits over the standard basis: the power (the number of gates whose output is one) and the \(P\)-activity (the number of gates having one on an input or on the output). For the first measure, the Shannon function for operators with \(n\) inputs and \(m\) outputs is shown to have order \(\Theta (n+m\log n)\) for \(1\le m\le 2^n\). For the second measure, we obtain an \(\Omega (n\log n)\) lower bound for almost all Boolean functions. Both results hold for the average and the maximum measures.
Keywords: Boolean functions, Boolean circuits, circuit power, circuit activity, Shannon function.
BibTeX
@article{IS-Kalachev2026,
author = {Kalachev, Gleb Vyacheslavovich},
title = {{Bounds on the Activity of Boolean Circuits Implementing Boolean Operators}},
journal = {Intelligent Systems. Theory and Applications},
year = {2026},
volume = {30},
number = {4},
pages = {164--167},
}
AMSBIB
\Bibitem{IS-Kalachev2026}
\by G.\,V.~Kalachev
\paper Bounds on the Activity of Boolean Circuits Implementing Boolean Operators
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 164--167
\lang In Russian
RU