An extension of Khrapchenko's theorem

DOI10.1016/0020-0190(91)90191-JMaRDI QIDQ753798zbMATH OpenOpenAlexWikidataFDO

Authors 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)

Recommendations

• Improvements on Khrapchenko's theorem
• Formula complexity of a linear function in a \(k\)-ary basis
• On convex complexity measures
• The effect of random restrictions on formula size
• The complexity of the parity function in unbounded fan-in, unbounded depth circuits

Cites work

• scientific article; zbMATH DE number 3889430 (Why is no real title available?)
• scientific article; zbMATH DE number 1142303 (Why is no real title available?)
• A Method for the Construction of Minimum-Redundancy Codes
• Complexity of the realization of a linear function in the class of -circuits
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits

Cited in

(12)

• An extension of Chesneau's theorem
• Smallest formulas for the parity of \(2^k\) variables are essentially unique
• Improvements on Khrapchenko's theorem
• An extension of a theorem of Sahab, Khan, and Sessa
• A dual result to Kharitonov's theorem
• On convex complexity measures
• Formula complexity of a linear function in a \(k\)-ary basis
• scientific article; zbMATH DE number 6128446 (Why is no real title available?)
• An extension of the Khinchin–Groshev theorem
• Smallest Formulas for Parity of 2 k Variables Are Essentially Unique
• scientific article; zbMATH DE number 4078803 (Why is no real title available?)
• On the meaning of works by V. M. Khrapchenko

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q753798)