Which Boolean Functions are Most Informative?

被引：0

作者：

Kumar, Gowtham R. ^{[1
]}

Courtade, Thomas A. ^{[1
]}

机构：

[1] Stanford Univ, Dept Elect Engn, Stanford, CA 94305 USA

来源：

2013 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS (ISIT) | 2013年

关键词：

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We introduce a simply stated conjecture regarding the maximum mutual information a Boolean function can reveal about noisy inputs. Specifically, let X-n be i.i.d. Bernoulli(1/2), and let Y-n be the result of passing X-n through a memoryless binary symmetric channel with crossover probability alpha. For any Boolean function b : {0, 1}(n) -> {0, 1}, we conjecture that I(b(X-n); Y-n) <= 1 - H(alpha). While the conjecture remains open, we provide substantial evidence supporting its validity.

引用

页码：226 / 230

页数：5

共 9 条

[1]

Allaart PC, 2011, REAL ANAL EXCH, V37, P1

[2]

[Anonymous], 2006, Elements of Information Theory

[3]

[Anonymous], 1999, ALL C COMM CONTR COM

[4] COMPRESSIONS AND ISOPERIMETRIC-INEQUALITIES [J].

BOLLOBAS, B ;

LEADER, I .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1991, 56 (01) :47-62

[5] The sic c function [J].

Guu, CJ .

DISCRETE MATHEMATICS, 2000, 213 (1-3) :163-167

[6]

Harper LH., 1966, J COMBINATORIAL THEO, V1, P385, DOI DOI 10.1016/S0021-9800(66)80059-5

[7]

Klotz J. G., 2012, ARXIV12077193

[8]

O'Donnell R, 2008, ACM S THEORY COMPUT, P569

[9] The regulatory network of E. coli metabolism as a Boolean dynamical system exhibits both homeostasis and flexibility of response [J].

Samal, Areejit ;

Jain, Sanjay .

BMC SYSTEMS BIOLOGY, 2008, 2

← 1 →