Abstract
A result of Krichevskii [3] and Hansel [1], concerning coverings of complete bipartite graphs is extended to hypergraphs, thus providing a lower bound on the lengths of Boolean formulas of a certain type realizing the threshold functions.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 103-105 |
| Number of pages | 3 |
| Journal | Discrete Mathematics |
| Volume | 27 |
| Issue number | 1 |
| DOIs | |
| State | Published - 1979 |
| Externally published | Yes |
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics