Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy

DOI10.1137/S0895480190283595MaRDI QIDQ4863976zbMATH OpenOpenAlexFDO

Authors Ilan Newman, A. Wigderson

Publication date 2 July 1996

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480190283595

zbMATH Keywords

circuit complexitygraph entropylow-complexity functions

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (05C99) Boolean functions (06E30)

Recommendations

• Entropy of contact circuits and lower bounds on their complexity
• The effect of random restrictions on formula size
• Entropy and enumeration of Boolean functions
• Publication:3033329
• scientific article; zbMATH DE number 4002123

Cited in

(13)

• scientific article; zbMATH DE number 4002123 (Why is no real title available?)
• Optimal linear perfect hash families
• Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings
• scientific article; zbMATH DE number 7204408 (Why is no real title available?)
• A stronger LP bound for formula size lower bounds via clique constraints
• On the limits of gate elimination
• Some intriguing upper bounds for separating hash families
• Separating hash families: a Johnson-type bound and new constructions
• Perfect hash families: Probabilistic methods and explicit constructions
• Communication Lower Bounds Via the Chromatic Number
• scientific article; zbMATH DE number 3877162 (Why is no real title available?)
• Entropy and enumeration of Boolean functions
• Linear Time Constructions of Some $$d$$-Restriction Problems

This page was built for publication: Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy

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