Joseph Frederick Traub, a leading figure in developing the field of computational complexity, passed away August 24, 2015, in Santa Fe.
At the time of his passing Traub, 83, was the Edwin Howard Armstrong Professor of Computer Science at Columbia University and an external professor of the Santa Fe Institute (SFI).
“Joe was a prodigious and wide-ranging thinker, a pioneer in computer science, an institution and department builder, and a scholar joyfully capable of living in many intellectual worlds at once,” says SFI President David Krakauer. “He brought to every problem a rigorous and open-minded balance of insight, an eye for specificity, and a willingness to explore unchartered landscapes of the mind — always with an aesthetic sensitivity. Many of us at SFI have counted on Joe for advice and friendship. We shall miss him very much.”
Traub spent his career at the frontiers of applied mathematics and computer science. He was known for advances in algorithmic thinking matched with emerging computational methods during the latter field’s formative period.
In 1959 while at Bell Laboratories, he had the key insight that the optimal (least computationally intensive) algorithm for solving a continuous problem depended on the available information. The application of this insight to the solution of nonlinear equations led to optimal iteration theory and his influential 1964 monograph Iterative Methods for the Solution of Equations, which is still in print.
In 1971, he became head of the computer science department at Carnegie Mellon University, a small department that at the time included such leading figures as Gordon Bell, Nico Haberman, Allen Newell, Raj Reddy, Herbert Simon and William Wulf. While at CMU, he and Henryk Woźniakowski pioneered the application of computational complexity to continuous scientific problems, a field that became known as information-based complexity.
In 1979, he became founding chairman of the computer science department at Columbia University and served in that role until 1989. While at Columbia, he co-authored the influential monographs A General Theory of Optimal Algorithms (1980), Information, Uncertainty, Complexity (1983), and Information-Based Complexity (1988).
In 1985, he became founding editor-in-chief of the Journal of Complexity. He continued in that role until his death.
In 1994, a collaborative paper with student Spassimir Paskov reported results that contradicted long-held practices in finance. In comparing the Monte Carlo method (MC) with the Quasi-Monte Carlo method (QMC) for calculating a collateralized mortgage obligation — a problem involving the approximation of a number of integrals in 360 dimensions — the pair showed that QMC always beat MC for this problem, whereas finance practitioners had always used MC for such problems. Today, QMC is widely used in the financial sector to value financial derivatives.
Among his more recent research interests was continuous quantum computing.
Traub was a longtime member of SFI’s research community. In the 1990s, he organized a series of SFI workshops on the Limits to Scientific Knowledge with the goal of enriching science in the same way that the work of Gödel and Turing on the limits of mathematics enriched that field. The workshops explored limits in various disciplines, including physics, economics, and geophysics.
“Joe was an incredibly original thinker,” says SFI Omidyar Fellow Josh Grochow. “He crossed over entrenched mathematical borders, as though they didn’t exist, to bring a new formalism of complexity to bear on the computational complexity of continuous algorithms. I was in the middle of an extended series of conversations with him spanning four or five different fields, and this seemed typical for him; I, and many others, will miss him dearly.”
“Joe was an exceptional member of the SFI community in so many ways, from the breadth and depth of his contributions to science and science policy, to a gift for friendship that he happily combined with a keen appreciation of food, wine, and life in Santa Fe,” says SFI Co-founder in Residence David Pines. “He will be very much missed, but our vivid memories of him will continue for years to come.”
He was author or editor of 10 books and some 120 papers in computer science, mathematics, physics, finance and economics. He also collaborated in creating a number of significant new algorithms, including the Jenkins-Traub Algorithm for Polynomial Zeros (still a widely used method included in many textbooks), as well as the Kung-Traub, Shaw-Traub, and Brent-Traub algorithms.
His honors included election to the National Academy of Engineering in 1985, the 1991 Emanuel R. Piore Gold Medal from IEEE, and the 1992 Distinguished Service Award of the Computer Research Association. He was a fellow of the American Association for the Advancement of Science, the Association for Computing Machinery, and the New York Academy of Sciences.
Traub is survived by two daughters and his wife, the author Pamela McCorduck.
