Conference paper
Global routing revisited
Michael D. Moffitt
ICCAD 2009
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.
Michael D. Moffitt
ICCAD 2009
B.K. Boguraev, Mary S. Neff
HICSS 2000
Chidanand Apté, Fred Damerau, et al.
ACM Transactions on Information Systems (TOIS)
Robert C. Durbeck
IEEE TACON