Lower estimate of potential for a class of volume circuits

Efimov Alexey Andreevich

Lower estimate of potential for a class of volume circuits

Efimov A. A.

Efimov Alexey Andreevich

junior researcher, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Chair of Mathematical Theory of Intellectual Systems

Published: 2023, vol. 27, issue 1, pp. 91–133

Download full text (In Russian)

Abstract

In this paper, volume circuits are considered, which are the embeddings of Boolean circuits in space. For volume circuits, the lower bound on the potential is obtained. Potential is a measure of circuit activity equal to the number of gates that produce one on a given input. It is shown that for almost all partial operators with n inputs and m outputs, the potential of the volume circuit that implements them is not less than \(\frac{m \sqrt[3]{d}}{\min^{2/3}(m, \log_2 d)}\), where d is the size of the domain.

Keywords: Boolean circuits, volume circuits, circuit complexity, circuit activity, potential.

BibTeX

@article{IS-Efimov2023,
  author  = {Efimov, Alexey Andreevich},
  title   = {{Lower estimate of potential for a class of volume circuits}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2023},
  volume  = {27},
  number  = {1},
  pages   = {91--133},
}

AMSBIB

\Bibitem{IS-Efimov2023}
\by A.\,A.~Efimov
\paper Lower estimate of potential for a class of volume circuits
\jour Intelligent Systems. Theory and Applications
\yr 2023
\vol 27
\issue 1
\pages 91--133
\lang In Russian

Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue