Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy

DOI10.1137/S0895480190283595zbMath0841.68081OpenAlexW2039213367MaRDI QIDQ4863976

Ilan Newman, Avi 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

graph entropycircuit complexitylow-complexity functions

Mathematics Subject Classification ID

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

Related Items (10)

On the limits of gate elimination ⋮ Separating Hash Families: A Johnson-type bound and New Constructions ⋮ Linear Time Constructions of Some $$d$$-Restriction Problems ⋮ Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings ⋮ A stronger LP bound for formula size lower bounds via clique constraints ⋮ Some intriguing upper bounds for separating hash families ⋮ Communication Lower Bounds Via the Chromatic Number ⋮ Unnamed Item ⋮ Optimal linear perfect hash families ⋮ Perfect hash families: Probabilistic methods and explicit constructions

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