A LOWER BOUND FOR PROBABILISTIC DISTRIBUTED ALGORITHMS

被引：7
作者：
PACHL, JK [1 ]
机构：
[1] UNIV WATERLOO,DEPT COMP SCI,WATERLOO N2L 3G1,ONTARIO,CANADA
来源：
JOURNAL OF ALGORITHMS | 1987年 / 8卷 / 01期
关键词：
D O I：
10.1016/0196-6774(87)90027-7
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
引用
收藏
页码：53 / 65
页数：13
相关论文
共 50 条
[21]   Lower-bound result on the power of genetic algorithms [J].
Park, Kihong .
Australian Electronics Engineering, 1994, 27 (02)
[22]   A lower bound on approximation algorithms for the closest substring problem [J].
Wang, Jianxin ;
Huang, Min ;
Chen, Jianer .
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PROCEEDINGS, 2007, 4616 :291-+
[23]   Statistical Algorithms and a Lower Bound for Detecting Planted Cliques [J].
Feldman, Vitaly ;
Grigorescu, Elena ;
Reyzin, Lev ;
Vempala, Santosh S. ;
Xiao, Ying .
JOURNAL OF THE ACM, 2017, 64 (02)
[24]   A LOWER-BOUND FOR RANDOMIZED LIST UPDATE ALGORITHMS [J].
TEIA, B .
INFORMATION PROCESSING LETTERS, 1993, 47 (01) :5-9
[25]   A LOWER-BOUND FOR RANDOMIZED ONLINE SCHEDULING ALGORITHMS [J].
CHEN, B ;
VANVLIET, A ;
WOEGINGER, GJ .
INFORMATION PROCESSING LETTERS, 1994, 51 (05) :219-222
[26]   AN IMPROVED LOWER BOUND FOR ONLINE BIN PACKING ALGORITHMS [J].
VANVLIET, A .
INFORMATION PROCESSING LETTERS, 1992, 43 (05) :277-284
[27]   A LOWER BOUND TO THE COMPLEXITY OF EUCLIDEAN AND RECTILINEAR MATCHING ALGORITHMS [J].
GRIGORIADIS, MD ;
KALANTARI, B .
INFORMATION PROCESSING LETTERS, 1986, 22 (02) :73-76
[28]   Statistical Algorithms and a Lower Bound for Detecting Planted Cliques [J].
Feldman, Vitaly ;
Grigorescu, Elena ;
Reyzin, Lev ;
Vempala, Santosh S. ;
Xiao, Ying .
STOC'13: PROCEEDINGS OF THE 2013 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2013, :655-664
[29]   A lower bound for DLL algorithms for k-SAT [J].
Pudlák, P ;
Impagliazzo, R .
PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2000, :128-136
[30]   Beating the Probabilistic Lower Bound on q-Perfect Hashing [J].
Xing, Chaoping ;
Yuan, Chen .
COMBINATORICA, 2023, 43 (02) :347-366
12345