KIAM Main page Web Library  •  Publication Searh  Русский 
Publication

Article collection "Mathematical Problems of Cybernetics" №4, Moscow, 1992
Authors: Grinchuk M.I.
Lower bound of symmetric Boolean function switching circuit complexity
Abstract:
A modification of a method from the author's previous work allows to establish explicitly given nonlinear lower bounds for the complexity of realizing a sequence of symmetric Boolean functions by switching circuits. In particular these bounds are obtained for the majority function, its negation, and the characteristic function of the n-dimensional hypercube middle layer.
Keywords:
switching circuits, complexity, symmetric Boolean function
Publication language: russian,  pages: 9 (p. 130-138)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Grinchuk Mikhail Ivanovich,  ,  МГУ им. М. В. Ломоносова, механико-математический факультет