Entropy and enumeration of Boolean functions

DOI10.1109/18.782146MaRDI QIDQ4503366zbMATH OpenOpenAlexFDO

Authors Nicholas Pippenger

Publication date 7 September 2000

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/18.782146

zbMATH Keywords

asymptotic formulascombinatorial enumerationHorn functionsmonotone Boolean functionsShannon entropy

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Boolean functions (06E30) Measures of information, entropy (94A17)

Recommendations

• Complexity of monotonic functions
• Entropy of contact circuits and lower bounds on their complexity
• scientific article; zbMATH DE number 3867232
• Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy
• Publication:3033329

Cited in

(11)

• Entropy of contact circuits and lower bounds on their complexity
• Random problems
• Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem
• A simple upper bound on the number of antichains in \([t]^n\)
• scientific article; zbMATH DE number 991156 (Why is no real title available?)
• Relations between powers of Dedekind numbers and exponential sums related to them
• Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy
• Dedekind's problem in the hypergrid
• Note on the number of antichains in generalizations of the Boolean lattice
• On Dedekind's problem, a sparse version of Sperner's theorem, and antichains of a given size in the Boolean lattice
• A dropping proof of an entropy inequality

This page was built for publication: Entropy and enumeration of Boolean functions

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