Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

Bounds on the Activity of Boolean Circuits Implementing Boolean Operators

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
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover