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 条
[31]   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
[32]   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
[33]   A linear lower bound on the unbounded error Probabilistic communication complexity [J].
Forster, J .
16TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2000, :100-106
[34]   LOWER BOUND EARTHQUAKE MAGNITUDE FOR PROBABILISTIC SEISMIC HAZARD EVALUATION [J].
MCCANN, MW ;
REED, JW .
NUCLEAR ENGINEERING AND DESIGN, 1990, 123 (2-3) :143-153
[35]   Beating the Probabilistic Lower Bound on q-Perfect Hashing [J].
Chaoping Xing ;
Chen Yuan .
Combinatorica, 2023, 43 :347-366
[36]   A linear lower bound on the unbounded error probabilistic communication complexity [J].
Forster, J .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2002, 65 (04) :612-625
[37]   A New Probabilistic Lower Bound on the Limited Packing Number of a Graph [J].
Mohammadi, Mehdi ;
Rad, Nader Jafari ;
Maghasedi, Mohammad .
UTILITAS MATHEMATICA, 2020, 114 :249-254
[38]   Lower Bound on Network Diameter for Distributed Function Computation [J].
Dai, H. K. ;
Toulouse, M. .
FUTURE DATA AND SECURITY ENGINEERING (FDSE 2019), 2019, 11814 :239-251
[39]   An efficient algorithm for reliability lower bound of distributed systems [J].
Department of Computer Science and Engineering, Harbin Institute of Technology, Harbin 150001, China .
World Acad. Sci. Eng. Technol., 2009, (40-42)
[40]   Computing Distributed Knowledge as the Greatest Lower Bound of Knowledge [J].
Pinzon, Carlos ;
Quintero, Santiago ;
Ramirez, Sergio ;
Valencia, Frank .
RELATIONAL AND ALGEBRAIC METHODS IN COMPUTER SCIENCE (RAMICS 2021), 2021, 13027 :413-432
12345