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 条

[1]

[Anonymous], 1987, COMPLEXITY BOOLEAN F

[2] OMEGA(N LOG N) LOWER BOUNDS ON LENGTH OF BOOLEAN-FORMULAS [J].

FISCHER, MJ ;

MEYER, AR ;

PATERSON, MS .

SIAM JOURNAL ON COMPUTING, 1982, 11 (03) :416-427

[3] ON THE SIZE OF SEPARATING SYSTEMS AND FAMILIES OF PERFECT HASH FUNCTIONS [J].

FREDMAN, ML ;

KOMLOS, J .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1984, 5 (01) :61-68

[4] CONSTRUCTING O(N LOG N) SIZE MONOTONE FORMULAS FOR THE KTH THRESHOLD FUNCTION OF N-BOOLEAN VARIABLES [J].

FRIEDMAN, J .

SIAM JOURNAL ON COMPUTING, 1986, 15 (03) :641-654

[5]

HANSEL G, 1964, CR HEBD ACAD SCI, V258, P6037

[6]

Khasin L. S., 1970, Soviet Physics - Doklady, V14, P1149

[7] NEW BOUNDS FOR PERFECT HASHING VIA INFORMATION-THEORY [J].

KORNER, J ;

MARTON, K .

EUROPEAN JOURNAL OF COMBINATORICS, 1988, 9 (06) :523-530

[8]

KORNER J, 1986, SIAM J ALGEBRA DISCR, V7, P560

[9]

KORNER J, 1973, 6TH T PRAG C INF THE, P441

[10]

KRAPCHENKO VM, 1972, MATH NOTES, V11, P474

← 1 2 →