Apostol Natsev, Alexander Haubold, et al.
MMSP 2007
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.
Apostol Natsev, Alexander Haubold, et al.
MMSP 2007
Liat Ein-Dor, Y. Goldschmidt, et al.
IBM J. Res. Dev
György E. Révész
Theoretical Computer Science
Eric Price, David P. Woodruff
FOCS 2011