Joseph (Joe) Frederick Traub

Co-pioneer of information-based computational complexity, Traub was the Edwin Howard Armstrong Professor of Computer Science at Columbia University and External Professor at the Santa Fe Institute. He held positions at Bell Laboratories, University of Washington, Carnegie Mellon University, and Columbia, as well as sabbatical positions at Stanford, Berkeley, Princeton, California Institute of Technology, and Technical University, Munich.

In 1959 he began his work on optimal iteration theory, culminating in his 1964 monograph, which is still in print. Subsequently Traub pioneered work with Henryk Woźniakowski on computational complexity applied to continuous scientific problems (information-based complexity). 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 research areas was continuous quantum computing.

Both his research and institution-building work had a major impact on the field of Computer Science. From 1971 to 1979 he headed the Computer Science Department at Carnegie Mellon and led it from a critical period to eminence. From 1979 to 1989 Traub was the founding Chair of the Computer Science Department at Columbia. From 1986 to 1992 he served as founding Chair of the Computer Science and Telecommunications Board, National Academies, and held the post again 2005–2009.

He was founding Editor-in-Chief of the Journal of Complexity in 1985 and continued in that capacity. This was probably the first journal to have complexity in the sense of computational complexity in its title. Starting with two issues and 285 pages in 1985, the Journal grew to publish six issues and nearly 1,000 pages.

He attended the Bronx High School of Science, where he was captain and first Board of the chess team. After graduating from City College of New York, Traub entered Columbia in 1954 intending to take a PhD in Physics. In 1955, on the advice of a fellow student, he visited the IBM Watson Research Lab at Columbia. At the time, this was one of the few places in the country where a student could gain access to computers. He found that his proficiency for algorithmic thinking matched perfectly with computers.

In 1957 he became a Watson Fellow through Columbia. His thesis was on Computational Quantum Mechanics, and his 1959 Ph.D. was in Applied Mathematics, since Computer Science degrees were not yet available. That same year he joined the Research Division of Bell Laboratories in Murray Hill, NJ.

One day a colleague asked him how to compute the solution of a certain problem. He could think of a number of ways to solve it. What was the optimal algorithm—that is, a method which would minimize the required computational resources? To his surprise, there was no theory of optimal algorithms, since the phrase computational complexity, which is the study of the minimal resources required to solve computational problems, was not introduced until 1965.

Traub had the key insight that the optimal algorithm for solving a continuous problem depended on the available information. This was eventually to lead to the field of Information-Based Complexity. The first area for which he applied his insight was the solution of nonlinear equations, and this research led to the 1964 monograph Iterative Methods for the Solution of Equations, which is still in print.

In 1966 he spent a sabbatical at Stanford, where he met a student named Michael Jenkins. Together they created the Jenkins-Traub Algorithm for Polynomial Zeros. This algorithm is still one of the most widely used methods for this problem and is included in many textbooks.

In 1970 he became a Professor at the University of Washington, and in 1971 he became Head of the Carnegie Mellon Computer Science Department. The Department was quite small, including Gordon Bell, Nico Haberman, Allen Newell, Raj Reddy, Herbert A. Simon, and William Wulf. Just prior to 1971 many faculty had left the Department to take positions elsewhere, but those professors who remained formed a core of world-class scientists recognized as leaders of the discipline. By 1978 the Department had grown to some 50 teaching and research faculty.

One of his Ph.D. students was H. T. Kung, now a chaired professor at Harvard. They created the Kung-Traub algorithm for comparing the expansion of an algebraic function and showed that computing the first N terms was no harder than multiplying two N-th degree polynomials. This problem had previously been worked on by Isaac Newton, who missed a key point.

In 1973 Traub invited Henryk Woźniakowski, now a tenured professor at both Columbia and the University of Warsaw, Poland, to visit CMU. They pioneered the field of information-based complexity, co-authoring three monographs and numerous papers. In 1978, while on sabbatical at Berkeley, he was recruited by Peter Likins to become founding Chairman of the Computer Science Department at Columbia and Edwin Howard Armstrong Professor of Computer Science, a chair he held from 1979 to 1989.

In 1980 he co-authored A General Theory of Optimal Algorithms, Academic Press, with Woźniakowski. This was the first research monograph on information-based complexity. Greg Wasilkowski subsequently joined him and Woźniakowski in two more monographs: Information, Uncertainty, Complexity, Addison-Wesley, 1983, and Information-Based Complexity, Academic Press, 1988.

In 1986, Traub was asked by the National Academies to form a Computer Science Board. The original name of the Board was the Computer Science and Technology Board (CSTB). Several years later CSTB was asked to also be responsible for telecommunications, so it was renamed the Computer Science and Telecommunications Board, preserving the abbreviation CSTB. The Board dealt with critical national issues in computer science and telecommunications, and he served as Founding Chair 1986–1992 and held the post again 2005–2009.

In 1990 he taught in the summer school of the Santa Fe Institute (SFI) and subsequently played a variety of roles there. In the nineties he organized a series of Workshops on Limits to Scientific Knowledge funded by the Alfred P. Sloan Foundation. The goal was to enrich science in the same way that the work of Gödel and Turing on the limits of mathematics enriched that field. There were workshops on limits in various disciplines: physics, economics, and geophysics. He ultimately served as an External Professor at SFI.

Starting in 1991 he was co-organizer of an international Seminar on "Continuous Algorithms and Complexity" at Schloss Dagstuhl, Germany. The ninth Seminar was held in September 2006. Many of the Seminar talks were on information-based complexity and, more recently, on continuous quantum computing.

Traub was invited by the Accademia Nazionale dei Lincei in Rome, Italy, to present the 1993 Lezione Lincee. He chose to give the cycle of six lectures at the Scuola Normale in Pisa and invited Arthur Werschulz to join him in publishing them. The lectures appeared in expanded form in Complexity and Information, Cambridge University Press, 1998.

In 1994 he asked a Ph.D. student, Spassimir Paskov, to compare the Monte Carlo method (MC) with the Quasi-Monte Carlo method (QMC) when calculating a collateralized mortgage obligation (CMO) he had obtained from Goldman Sachs. This involved the numerical approximation of a number of integrals in 360 dimensions. To the surprise of the research group, Paskov reported that QMC always beat MC for this problem. People in finance had always used MC for such problems, and the experts in number theory believed QMC should not be used for integrals of dimension greater than 12.

Traub and Paskov reported their results to a number of Wall Street firms, to considerable initial skepticism. They first published the results in "Paskov and Traub, Faster Evaluation of Financial Derivatives, Journal of Portfolio Management" 22, 1995, 113–120. The theory and software was greatly improved by Anargyros Papageorgiou. Today QMC is widely used in the financial sector to value financial derivatives, though it is not a panacea for all high-dimensional integrals, and research continued on the characterization of problems for which QMC is superior to MC.

In 1999 he received the Mayor's Medal for Science and Technology. Decisions regarding this award are made by the New York Academy of Sciences, and the medal was awarded by Mayor Rudy Giuliani in a ceremony at Gracie Mansion, the home of New York City's mayor.

Moore's law is an empirical observation that the number of features on a chip doubles roughly every 18 months. This held since the early 1960s and was responsible for the computer and telecommunications revolution. It was widely believed that Moore's law would cease to hold within 10–15 years using silicon technology, generating interest in new technologies such as quantum computing—that is, building a computer using the principles of quantum mechanics. Traub and his colleagues undertook work on continuous quantum computing, motivated by the fact that most problems in physical science, engineering, and mathematical finance have continuous mathematical models.

In 2005 he donated some 100 boxes of archival material to the Carnegie Mellon University Library, a collection that was subsequently digitized. The U.S. patents US5940810 and US0605837 were issued to Traub et al. for the FinDer Software System and were assigned to Columbia University. These patents cover an application of a well-known technique (low discrepancy sequences) to a well-known problem (valuation of securities).

Besides those already mentioned, he was the recipient of numerous honors and distinctions, including: Member, National Academy of Engineering, 1985; Sherman Fairchild Distinguished Scholar, California Institute of Technology, 1991–92; Distinguished Senior Scientist Award, Alexander von Humboldt Foundation, 1992, 1998; Member, Scientific Council, Institut en Recherche en Informatique, Paris, France, 1976–1980; First Prize, Ministry of Education, Poland, for the research monograph "Information-Based Complexity," 1989; 1991 Emanuel R. Piore Medal, IEEE; 1992 Distinguished Service Award, Computing Research Association; Fellow: American Association for the Advancement of Science, 1971; ACM, 1994; New York Academy of Sciences, 1999; American Mathematical Society, 2012; Festschrift for Joseph F. Traub, Academic Press, 1993, Elsevier, 2004; and Honorary Doctorate of Science, University of Central Florida, 2001.

Traub was the author or editor of ten monographs and some 120 papers in computer science, mathematics, physics, finance, and economics, including: Iterative Methods for the Solution of Equations, Prentice Hall, 1964, reissued Chelsea Publishing Company, 1982; Russian translation MIR, 1985; reissued American Mathematical Society, 1998; Algorithms and Complexity: New Directions and Recent Results, (editor) Academic Press, 1976; Information-Based Complexity, Academic Press, 1988 (with G. Wasilkowski and H. Woźniakowski); and Complexity and Information, Cambridge University Press, 1998 (with A. G. Werschulz), Japanese translation, 2000.

He was also the author or co-author of several notable papers, including: "Variational Calculations of the 23 P State of Helium," Phys. Rev. 116, 1959, 914–919; "The Future of Scientific Journals," Science 158, 1966, 1153–1159 (with W. S. Brown and J. R. Pierce); "Computational Complexity of Iterative Processes," SIAM Journal on Computing 1, 1972, 167–179; "Parallel Algorithms and Parallel Computational Complexity," Proceedings IFIP Congress, 1974, 685–687; "On the Complexity of Composition and Generalized Composition of Power Series," SIAM Journal on Computing 9, 1980, 54–66 (with R. Brent); "Information-Based Complexity," Nature 327, July 1987, 29–33 (with E. Packel); and "Path Integration on a Quantum Computer," Quantum Information Processing, 2003, 365–388 (with H. Woźniakowski).

He lived in Manhattan and Santa Fe with his wife, noted author Pamela McCorduck, whose books include Machines Who Think, The Fifth Generation, The Universal Machine, Aaron's Code, and The Futures of Women. He had two daughters, Claudia Traub-Cooper and Hillary Spector.