B. Wagle
EJOR
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.
B. Wagle
EJOR
Matthias Kaiserswerth
IEEE/ACM Transactions on Networking
Yigal Hoffner, Simon Field, et al.
EDOC 2004
Alessandro Morari, Roberto Gioiosa, et al.
IPDPS 2011