Poly-logarithmic Independence Fools Bounded-Depth Boolean Circuits

被引：23

作者：

Braverman, Mark ^{[1
]}

机构：

[1] Univ Toronto, Toronto, ON M5S 1A1, Canada

来源：

COMMUNICATIONS OF THE ACM | 2011年 / 54卷 / 04期

关键词：

SET;

D O I：

10.1145/1924421.1924446

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

[No abstract available]

引用

页码：108 / 115

页数：8

共 14 条

[1] A FAST AND SIMPLE RANDOMIZED PARALLEL ALGORITHM FOR THE MAXIMAL INDEPENDENT SET PROBLEM [J].

ALON, N ;

BABAI, L ;

ITAI, A .

JOURNAL OF ALGORITHMS, 1986, 7 (04) :567-583

[2]

BAZZI LMJ, 2009, SIAM J COMP IN PRESS

[3] Polylogarithmic Independence Fools AC0 Circuits [J].

Braverman, Mark .

JOURNAL OF THE ACM, 2010, 57 (05)

[4]

De Wolf R., 2008, GRADUATE SURVEYS THE

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

FURST, M ;

SAXE, JB ;

SIPSER, M .

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

[6]

HASTAD J, 1986, P 18 ANN ACM S THEOR, P20

[7] SET OF ALMOST DETERMINISTIC K-INDEPENDENT RANDOM-VARIABLES [J].

JOFFE, A .

ANNALS OF PROBABILITY, 1974, 2 (01) :161-162

[8] APPROXIMATE INCLUSION-EXCLUSION [J].

LINIAL, N ;

NISAN, N .

COMBINATORICA, 1990, 10 (04) :349-365

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

LINIAL, N ;

MANSOUR, Y ;

NISAN, N .

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

[10] PSEUDORANDOM BITS FOR CONSTANT DEPTH CIRCUITS [J].

NISAN, N .

COMBINATORICA, 1991, 11 (01) :63-70

← 1 2 →