ON THE MEANING OF WORKS BY V. M. KHRAPCHENKO

DOI10.17223/20710410/48/10zbMath1459.01025OpenAlexW3047423937MaRDI QIDQ5151450

Sergey B. Gashkov, Igor S. Sergeev

Publication date: 17 February 2021

Published in: Prikladnaya Diskretnaya Matematika (Search for Journal in Brave)

Full work available at URL: http://mathnet.ru/eng/pdm709

zbMATH Keywords

depthsymmetric functionscircuit delaylower complexity boundsKhrapchenko methodparallel adder

Mathematics Subject Classification ID

Biographies, obituaries, personalia, bibliographies (01A70)

Cites Work

• Network delay in a model with inputs of functional elements
• Complexity and depth of formulas for symmetric Boolean functions
• Boolean function complexity. Advances and frontiers.
• Lower bounds on the formula complexity of a linear Boolean function
• Depth and polynomial equivalence of formulas for closed classes of two- valued logic
• Size-depth tradeoff in non-monotone Boolean formulae
• The complexity of the realization of symmetrical functions by formulae
• Size-depth tradeoff in monotone Boolean formulae
• Shallow circuits and concise formulae for multiple addition and multiplication
• Complexity of the realization of a linear function in the class of \(\Pi\)-circuits
• Optimal algorithms for parallel polynomial evaluation
• The fundamental difference between depth and delay
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Parallelizable algebras
• Efficient Parallel Evaluation of Boolean Expressions
• The Shrinkage Exponent of de Morgan Formulas is 2
• Binary Adder Circuits of Asymptotically Minimum Depth, Linear Size, and Fan-Out Two
• New inequality relations between depth and delay
• A simplified proof of a lower complexity estimate
• On the Addition of Binary Numbers
• On the Parallel Evaluation of Polynomials
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item