Santa Fe Institute

In memoriam: Joseph Traub

Aug. 25, 2015 8:44 a.m.

Joseph Traub, a leading figure in developing the field of computational complexity, passed away Monday morning, 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.

“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’s memorial service will be held Friday, September 4, 10:00 am, at the United Church (Arroyo Chamiso and St. Michael’s Drive, 505.988.3295) in Santa Fe.

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 ten 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.

The family has asked that anyone who would like to make memorial gifts to make them to the Santa Fe Institute or the Santa Fe Conservation Trust.

Read the obituary in The New York Times (August 26, 2015)

Read the obituary in Scientific Computing (August 27, 2015)

The Santa Fe Institute invites friends and colleagues of Joseph Traub to share memories of his life and career in the comments below (moderated).

All SFI NewsAbout SFIFollow SFISupport SFISFI Home

Comments - post a comment

joanna hess - Aug. 25, 2015, 3:33 p.m.



Marita Prandoni - Aug. 26, 2015, 2:59 p.m.

I was Joe’s assistant over the past several years while he spent time at his home in Santa Fe. While I am aware of the academic legacy he forged, I can say that Joe also possessed great relational intelligence: He was humorous, kind and generous. When I left the receptionist position at SFI and began working as Brian Arthur’s assistant, I was assigned a desk near the bathroom on north campus. Joe joked that I had been promoted to “die Toilettenfrau,” which still makes me laugh.

Up until very recently, Joe was physically robust and enjoyed getting out to hike in the mountainous vicinity of his home, always setting goals for his outings in time, pace and distance. We shared a love of nature, and while helping him organize his files we would identify the birds that came to the feeder outside his office door.

Born in Karlsruhe, Joe had a fine command of German, and we would frequently chat in German. While we worked, we would listen to the classical music broadcast from Germany and Switzerland on iTunes, appreciating not only the music but also the host’s crisp enunciation during the news breaks.

I’ll miss those hours in Joe’s company. He was a lifelong learner and an inspiration.

Richard Karp - Aug. 27, 2015, 5:53 a.m.

I got to know Joe and Pamela well during their many summers in Berkeley, and was often their guest in New York City. I admired Joe's intellectual daring and breadth, his personal charm and genuine concern for others, his strenuous efforts to advance the field of computer science, his appreciation of the finer things in life, and his love of the outdoors. It is a shock that such a vigorous presence has been taken away so suddenly.

Art Werschulz - Aug. 31, 2015, 8:32 a.m.

I was in a state of shock when I learned of Joe's untimely death last week.

Joe was my PhD advisor at Carnegie-Mellon, back in the 1970s. He was also the head of the research group in information-based complexity at Columbia, where I have been a participant. We co-authored one book (and one paper). Moreover, I have served on the Editorial Board of the Journal of Complexity. It's been a real privilege to have worked with him and to have known him, in all these roles.

Along with a lot of other people, I'm certainly going to miss Joe's presence.

Peter Zadrozny - Sept. 1, 2015, 4:54 p.m.

I'm saddened to read this news. I never met Prof. Traub or corresponded with him. However, his article "The Algebraic Theory of Matrix Polynomials", 1976, with J.E. Dennis and R.P. Weber helped me greatly in my work on the analysis of dynamic economic systems. Rather than have to read thick books, I was able to quickly learn what I needed to learn from this superb short article. Thank you, Prof. Traub.

I feel a certain kinship as I also received my bachelor's degree from City College of New York (mathematics and economics).

Steven Damelin - Sept. 1, 2015, 5:43 p.m.

I am very saddened to hear of Joe's untimely death. I first met Joe at an Oberwolfach conference about 11 years ago where on the train on the way to the conference, he sat down with me and carefully explained to me some beautiful ideas in the subject of Tractability of Function Approximation Problems.

I will miss him greatly.

John Dennis - Sept. 4, 2015, 5:34 p.m.

I met Joe at the Iowa City SIAM meeting beer party in 1966. I had just completed my phd, and this was my first scientific meeting. My conversation with Joe left a lasting impression. He asked what my dissertation had been about. When I told him, his next question was why I had done that. Every fresh phd should be asked that, but they should be prepared to give a better answer than I gave.

Later Joe and I coauthored some papers with my Cornell student Roy Weber, so I guess he forgave me my lame answer to his first question. Bye, Joe.

Post a Comment

News Media Contact

  • John German
  • Director of Communications
  • (505) 946-2798


Parallax newsletter
Bulletin magazine
Follow SFI

SFI in the News