Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy

DOI10.1137/S0895480190283595zbMATH Open0841.68081OpenAlexW2039213367MaRDI QIDQ4863976FDOQ4863976

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

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

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)

Cited In (13)

• Optimal linear perfect hash families
• Title not available (Why is that?)
• Separating Hash Families: A Johnson-type bound and New Constructions
• 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
• Perfect hash families: Probabilistic methods and explicit constructions
• Communication Lower Bounds Via the Chromatic Number
• Title not available (Why is that?)
• Entropy and enumeration of Boolean functions
• Linear Time Constructions of Some $$d$$-Restriction Problems
• Title not available (Why is that?)
• Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings

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)