学术探索
学术期刊
新闻热点
数据分析
智能评审

Complexity measures and decision tree complexity: a survey

被引：340
作者：
Buhrman, H
de Wolf, R
机构：
[1] CWI, NL-1098 SJ Amsterdam, Netherlands
[2] Univ Amsterdam, ILLC, NL-1018 TV Amsterdam, Netherlands
来源：
THEORETICAL COMPUTER SCIENCE | 2002年 / 288卷 / 01期
关键词：
decision tree complexity; complexity measures for Boolean functions; randomized computing; quantum computing;
D O I：
10.1016/S0304-3975(01)00144-X
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We discuss several complexity measures for Boolean functions: certificate complexity, sensitivity, block sensitivity, and the degree of a representing or approximating polynomial. We survey the relations and biggest gaps known between these measures, and show how they give bounds for the decision tree complexity of Boolean functions on deterministic, randomized, and quantum computers. (C) 2002 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：21 / 43
页数：23
相关论文
共 49 条
[1]   Note on quantum black-box complexity of almost all Boolean functions [J].
Ambainis, A .
INFORMATION PROCESSING LETTERS, 1999, 71 (01) :5-7
[2]  
Ambainis A, 2000, LECT NOTES COMPUT SC, V1770, P133
[3]   Quantum lower bounds by polynomials [J].
Beals, R ;
Buhrman, H ;
Cleve, R ;
Mosca, M ;
de Wolf, R .
39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1998, :352-361
[4]  
Beigel R., 1993, Proceedings of the Eighth Annual Structure in Complexity Theory Conference (Cat. No.93CH3281-3), P82, DOI 10.1109/SCT.1993.336538
[5]   Sensitivity vs block sensitivity (an average-case study) [J].
Bernasconi, A .
INFORMATION PROCESSING LETTERS, 1996, 59 (03) :151-157
[6]  
Blum M., 1987, 28th Annual Symposium on Foundations of Computer Science (Cat. No.87CH2471-1), P118, DOI 10.1109/SFCS.1987.30
[7]   The average sensitivity of bounded-depth circuits [J].
Boppana, RB .
INFORMATION PROCESSING LETTERS, 1997, 63 (05) :257-261
[8]  
BUHRMAN H, 1999, COMMUNICATION COMPLE
[9]  
BUHRMAN H, 1999, P 40 IEEE S FDN COMP, P358
[10]   UPPER AND LOWER TIME-BOUNDS FOR PARALLEL RANDOM-ACCESS MACHINES WITHOUT SIMULTANEOUS WRITES [J].
COOK, S ;
DWORK, C ;
REISCHUK, R .
SIAM JOURNAL ON COMPUTING, 1986, 15 (01) :87-97
12345