LOWER BOUNDS ON FORMULA SIZE OF BOOLEAN FUNCTIONS USING HYPERGRAPH ENTROPY

被引：18

作者：

NEWMAN, I ^{[2
]}

WIGDERSON, A

机构：

[1] UNIV HAIFA,DEPT MATH & COMP SCI,IL-31905 HAIFA,ISRAEL

[2] HEBREW UNIV JERUSALEM,DEPT COMP SCI,IL-91904 JERUSALEM,ISRAEL

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 1995年 / 8卷 / 04期

关键词：

BOOLEAN FUNCTIONS; GRAPH ENTROPY; CIRCUIT COMPLEXITY;

D O I：

10.1137/S0895480190283595

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Korner defined the notion of graph entropy. He used it to simplify the proof of the Fredman-Komlos lower bound for the family size of perfect hash functions. We use this information-theoretic notion to obtain a general method for formula size lower bounds. This method can be applied to low-complexity functions for which the other known general methods do not apply.

引用

页码：536 / 542

页数：7

共 18 条

[11]

Krichevskii R.E, 1964, SOV PHYS DOKL, V8, P770

[12]

Nechiporuk E.I., 1966, SOVIET MATH DOKL, P999

[13] INFORMATION-THEORETIC METHOD IN COMBINATORIAL THEORY [J].

PIPPENGER, N .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1977, 23 (01) :99-104

[14] IMPROVED BOUNDS FOR COVERING COMPLETE UNIFORM HYPERGRAPHS [J].

RADHAKRISHNAN, J .

INFORMATION PROCESSING LETTERS, 1992, 41 (04) :203-207

[15]

RADHAKRISHNAN J, 1991, 32ND P IEEE S F COMP, P314

[16]

RAZBOROV AA, 1990, BOOLEAN FUNCTION COM, P76

[17] COVERING PROBLEM OF COMPLETE UNIFORM HYPERGRAPHS [J].

SNIR, M .

DISCRETE MATHEMATICS, 1979, 27 (01) :103-105

[18]

[No title captured]

← 1 2 →