Chapter 8: Joseph F. Traub: Information-Based Complexity

Joseph F. Traub is the Edwin Howard Armstrong Professor of Computer Science at Columbia University and External Professor, Santa Fe Institute http://www.cs.columbia.edu/~traub. He is the author or editor of 10 monographs and some 140 papers on computer science, mathematics, physics, finance and economics. In 1959 he began his work on the optimal iteration theory culminating in the 1964 monograph which is still in print. Subsequently he pioneered work with Henryk Wozniakowski on optimal algorithms and computational complexity applied to continuous scientific problems (IBC ). He collaborated in creating significant new algorithms including the Jenkins–Traub algorithm for polynomial zeros, as well as the Kung–Traub, Shaw–Traub, and Brent–Traub algorithms. One of his current research areas is quantum computing. From 1971 to 1979 he headed the Computer Science department at Carnegie Mellon University (CMU) and led it from a critical period to eminence (see the Joseph Traub digital archive at CMU at http://diva.library.cmu.edu/traub). From 1979 to 1989, he was the founding chair of the Computer Science department at Columbia University. From 1986 to 1992 he served as founding chair of the Computer Science and Telecommunications Board (CSTB), National Academies and served as chair again 2005–2009. Traub is the founding editor-in-chief of the Journal of Complexity (since 1985)…