The average sensitivity of bounded-depth circuits

被引：74

作者：

Boppana, RB

机构：

来源：

INFORMATION PROCESSING LETTERS | 1997年 / 63卷 / 05期

基金：

美国国家科学基金会;

关键词：

computational complexity; Boolean circuits;

D O I：

10.1016/S0020-0190(97)00131-2

中图分类号：

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

学科分类号：

0812 ;

摘要：

The average sensitivity of a Boolean circuit is the expected number of input bits that, when flipped, change the output of the circuit, starting with a random input setting. We show that unbounded-fanin circuits of depth d and size s have average sensitivity O(log s)(d-1). This bound is asymptotically tight. (C) 1997 Elsevier Science B.V.

引用

页码：257 / 261

页数：5

共 9 条

[1] SIGMA-11-FORMULAE ON FINITE STRUCTURES [J].

AJTAI, M .

ANNALS OF PURE AND APPLIED LOGIC, 1983, 24 (01) :1-48

[2]

BOPPANA RB, 1990, HDB THEORETICAL COMP, VA, P759

[3] PARITY, CIRCUITS, AND THE POLYNOMIAL-TIME HIERARCHY [J].

FURST, M ;

SAXE, JB ;

SIPSER, M .

MATHEMATICAL SYSTEMS THEORY, 1984, 17 (01) :13-27

[4]

HASTAD J, 1989, ADV COMPUTING RES, V5, P143

[5]

Hastad Johan, 1987, Computational limitations for small-depth circuits

[6]

Khrapchenko V.M., 1971, Math. Notes Acad. of Sci. USSR, V10, P474, DOI 10.1007/BF01747074

[7] CONSTANT DEPTH CIRCUITS, FOURIER-TRANSFORM, AND LEARNABILITY [J].

LINIAL, N ;

MANSOUR, Y ;

NISAN, N .

JOURNAL OF THE ACM, 1993, 40 (03) :607-620

[8] THE COMPUTATIONAL-COMPLEXITY OF UNIVERSAL HASHING [J].

MANSOUR, Y ;

NISAN, N ;

TIWARI, P .

THEORETICAL COMPUTER SCIENCE, 1993, 107 (01) :121-133

[9] LIMITING NEGATIONS IN CONSTANT DEPTH CIRCUITS [J].

SANTHA, M ;

WILSON, C .

SIAM JOURNAL ON COMPUTING, 1993, 22 (02) :294-302

← 1 →