Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
We prove an Ω(log log(1/ε)) lower bound on the depth of any computation tree and any RAM program with operations {+, -, *, /, ⌊·⌋, not, and, or, xor}, unlimited power of answering YES/NO questions, and constants {0,1} that computes √x to accuracy ε, for all x ∈ [1,2]. Since the Newton method achieves such an accuracy in O(log log(1/ε)) depth, our bound is tight. © 1997 Published by Elsevier Science B.V.
Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics
Eric Price, David P. Woodruff
FOCS 2011
Xiaozhu Kang, Hui Zhang, et al.
ICWS 2008