Joel L. Wolf, Mark S. Squillante, et al.
IEEE Transactions on Knowledge and Data Engineering
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.
Joel L. Wolf, Mark S. Squillante, et al.
IEEE Transactions on Knowledge and Data Engineering
György E. Révész
Theoretical Computer Science
Ohad Shamir, Sivan Sabato, et al.
Theoretical Computer Science
Eric Price, David P. Woodruff
FOCS 2011