An extension of Khrapchenko's theorem

DOI10.1016/0020-0190(91)90191-JzbMath0716.94016OpenAlexW1967322922WikidataQ60299190 ScholiaQ60299190MaRDI QIDQ753798

Uri Zwick

Publication date: 1991

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90191-j

zbMATH Keywords

computational complexityHuffman codingformula complexity of the parity functionlower bounds on the formula complexity of Boolean functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (3)

Smallest Formulas for Parity of 2 k Variables Are Essentially Unique ⋮ Improvements on Khrapchenko's theorem ⋮ Smallest formulas for the parity of \(2^k\) variables are essentially unique

Cites Work

• Complexity of the realization of a linear function in the class of \(\Pi\)-circuits
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• A Method for the Construction of Minimum-Redundancy Codes
• Unnamed Item
• Unnamed Item

This page was built for publication: An extension of Khrapchenko's theorem