An extension of Khrapchenko's theorem

DOI10.1016/0020-0190(91)90191-JzbMATH Open0716.94016OpenAlexW1967322922WikidataQ60299190 ScholiaQ60299190MaRDI QIDQ753798FDOQ753798

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

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

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)

Cites Work

• A Method for the Construction of Minimum-Redundancy Codes
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Title not available (Why is that?)
• Complexity of the realization of a linear function in the class of \(\Pi\)-circuits
• Title not available (Why is that?)

Cited In (12)

• An extension of Chesneau's theorem
• Smallest formulas for the parity of \(2^k\) variables are essentially unique
• An extension of a theorem of Sahab, Khan, and Sessa
• Improvements on Khrapchenko's theorem
• A dual result to Kharitonov's theorem
• On convex complexity measures
• Formula complexity of a linear function in a \(k\)-ary basis
• Title not available (Why is that?)
• An extension of the Khinchin–Groshev theorem
• Smallest Formulas for Parity of 2 k Variables Are Essentially Unique
• Title not available (Why is that?)
• 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)