In Memoriam: Joseph F. Traub

Joseph F. Traub, a pioneering computer scientist and founder of the Computer Science department at Columbia University, died Monday, August 24, 2015 in Santa Fe, NM. He was 83. Most recently the Edwin Howard Armstrong Professor of Computer Science, Traub was an early pioneer in computer science years before such a discipline existed, and he would do a lot to shape the field.

Traub was most known for his work on optimal algorithms and computational complexity applied to continuous scientific problems. In collaboration with Henryk Woźniakowski, he created the field of information-based complexity, where the goal is to understand the cost of solving problems when information is partial, contaminated, or priced. Applications for information-based complexity are diverse and include differential and integral equations, continuous optimization, path integrals, high-dimensional integration and approximation, and low-discrepancy sequences.

Understanding the role of information about a problem was a unifying theme of Traub’s contributions to a number of diverse areas of computing. Often collaborating with others, he created significant new algorithms, including the Jenkins-Traub algorithm for polynomial zeros, the Kung-Traub algorithm for comparing the expansion of an algebraic function, and the Shaw-Traub algorithm to increase computational speed. He authored or edited ten monographs and some 120 papers in computer science, mathematics, physics, computational finance, and quantum computing.

Apart from his scientific research, he had a major role in building and leading organizations that promoted computer science. In 1971, at the age of 38, he was appointed chair of the computer science department at Carnegie Mellon University (CMU), overseeing its expansion from fewer than 10 professors to 50, and making it one of the strongest computer science departments in the country. Based on his achievements at CMU, Columbia University in 1979 extended an offer to Traub to found the University’s Computer Science department. He accepted the offer and chose to locate Computer Science within the Engineering School, which at the time offered a single computer, only three tenured faculty members teaching computer science, and a huge demand for computer classes.

After securing a $600,000 gift from IBM (which later provided another $4 million), he was able to add faculty and attract top students. Within a year the department was awarding bachelor’s and master’s degrees as well as PhDs. He would chair the department until 1989.

In 1982 he oversaw the construction of the Computer Science Building, working closely with architects to come up with a final design that would later win awards.

Traub liked building things from scratch. In 1985 while still chair of the Computer Science department, he became the founding editor-in-chief of the Journal of Complexity (a position he held at the time of his death). In 1986, he founded the Computer Science and Technology Board (CSTB) of the National Research Council, serving as its chair from 1986 until 1992 and again in 2005 and 2009.

His awards and honors are many and include election to the National Academy of Engineering in 1985, the 1991 Emanuel R. Piore Gold Medal from IEEE, and the 1992 Distinguished Service Award from the Computer Research Association (CRA). He is a Fellow of the Association for Computing Machinery (ACM), the American Association for the Advancement of Science (AAAS), the Society for Industrial and Applied Mathematics (SIAM), and the New York Academy of Sciences (NYAS). He was selected by the Accademia Nazionale dei Lincei in Rome to present the 1993 Lezione Lincee, a cycle of six lectures. Traub received the 1999 Mayor’s Award for Excellence in Science and Technology, an award presented by Mayor Rudy Giuliani.

In 2012, his 80th birthday was commemorated by a symposium at Columbia’s Davis Auditorium to celebrate his research and contributions to computer science.

Traub’s “contributions to Columbia’s Computer Science Department have been instrumental in establishing the strong foundation of excellence of our Computer Science department today, enabling our ongoing frontier leadership in this field,” said Dean Mary C. Boyce. “Joe will be sorely missed by all of us at Columbia and by the computer science community across the globe.”

Traub always described himself as lucky: Lucky in his early life that his parents were able to flee Nazi Germany in 1939 and settle in New York City; that he had a knack for math and problem-solving just when those skills were needed; that a fellow student’s prescient suggestion led him to visit IBM’s Watson Laboratories where he first encountered computers. And lucky to be among the first to enter a new, unexplored field when he had the ambition to make new discoveries and a hunger to do something significant. In an interview recalling his life, he once said “I’m almost moved to tears but who could have expected such a wonderful life and such a wonderful career.”

That he returned to New York City to found Columbia’s computer science department is entirely appropriate. He attended both Bronx High School of Science and City College of New York (earning degrees in math and physics) before entering Columbia University in 1954 intent on a PhD in theoretical physics. That plan changed when he discovered computers, not at Columbia—which had no computers—but at the IBM Watson lab then located in Casa Hispanica, just off campus at 612 W. 116th Street. He was hired there as a fellow, gaining the perk of unlimited computer time.

In 1959 he earned his PhD under the Committee of Applied Mathematics at Columbia. After his first choice to work on a chess problem was rejected, he proposed instead a quantum problem that involved six months of programing to calculate the ground energy state of a helium atom, correct to four decimal points.

After graduating Columbia, Traub went to work at Bell Labs then in its “golden 60s” when researchers were given wide latitude to choose projects and conduct pure research. It was there that a colleague one day walked into his office with a problem. Could Traub find the zero of a function that involved an integral? Mulling over the problem led to two observations: one, it was expensive to compute the function; and two, there were lots of ways of solving it. His thinking about how to select the best, most optimal algorithm culminated in his 1964 monograph Iterative Methods for the Solution of Equations. It was the start of his career with many publications to come.

His luck extended to his personal life. He was married to Pamela McCorduck, a noted author who also taught science writing at Columbia. He enjoyed skiing, tennis, hiking, travel, and good food.

He regularly spent his summers in Santa Fe, where he was an External Professor at the Santa Fe Institute and played a variety of roles over the years, often organizing workshops to bring together those working in science and math. It was in Santa Fe where he died Monday morning, unexpectedly and quickly, after having made plans to travel to Germany, Poland, and CMU. He is survived by his wife Pamela and two daughters, Claudia Traub-Cooper and Hillary Spector.

Joseph Traub was an important and valued member of the Computer Science department he founded. He will be missed by faculty, staff, and students.

– Linda Crane