Traub, most recently the Edwin Howard Armstrong Professor of Computer Science at Columbia University, was known for his research on computational complexity and quantum computing and for his academic leadership in computer science — expanding and strengthening CSD in the 1970s and later founding the computer science department at Columbia.
After spending much of his early career at Bell Laboratories, Traub was teaching at the University of Washington when he was offered the position of CSD Head in 1971. He replaced Alan Perlis, the first head of CSD, who had moved on to Yale University.
"It was a small department then," recalled Raj Reddy, who was an assistant professor at the time and would later become dean of the School of Computer Science. Following the loss of Perlis and several other faculty members, the six-year-old department had only three tenured professors and only about 10 faculty members in total.
"He had to build up the department from this small size to a larger base without straining the university," Reddy said of the challenge facing Traub.
CSD's future may have been uncertain, but Traub, then age 38, was undaunted.
"The department was still a jewel, even though half of the faculty had left, and my number one priority was, 'Got to hire some great faculty,'" Traub told Jason Togyer, editor of The Link, in an interview last year.
"They were working on some very sexy stuff here with parallel processing, for instance," Traub said. "And even though they had lost some faculty members, Allen Newell and Herb Simon were still here and they were giants."
He wasted no time moving the department into the then-new Science Hall, now Wean Hall, which provided plenty of office space. DARPA accounted for the vast majority of the department's funding, so Traub worked with the faculty to diversify and increase external funding.
By the time he left in 1979 for Columbia, where he modeled its new Department of Computer Science after CMU's, the CSD faculty numbered around 50. The new recruits included many who would become leaders at CMU, including Mary Shaw and Dan Siewiorek.
"I have always admired Joe's leadership style, which was strongly rooted in the Reasonable Person Principle," said Shaw, the Alan J. Perlis University Professor of Computer Science and a National Medal of Technology and Innovation recipient. "He made decisions by building consensus, sometimes by public meetings preceded by position papers, sometimes by walking around and talking to people. He rarely, if ever, was the main public advocate for a position, but he rather shepherded the discussion to a reasonable outcome."
In his resignation letter, Traub noted that CSD was in excellent shape. "Its faculty is distinguished, its students outstanding, its funding large and secure. It is a group of which I'm proud to have been a part.
"I have spent some of the most significant years of my life at Carnegie Mellon University. You will always be close to my heart."
Born in Karlsruhe, Germany, he grew up in New York City, attending the Bronx High School of Science and City College of New York. Though he entered Columbia to study theoretical physics, he discovered his love for computing at the nearby IBM Watson lab and ultimately earned a Ph.D. in applied mathematics in 1959.
Known for his work on optimal algorithms and computational complexity, Traub collaborated with a number of researchers to create significant new algorithms. His work with Shaw, for instance, resulted in the Shaw-Traub algorithm to increase computational speed, while his work with H.T. Kung, another of his hires at CMU and now a professor at Harvard University, produced the Kung-Traub algorithm for comparing the expansion of an algebraic function.
His awards and honors include election to the National Academy of Engineering, IEEE's Emanuel R. Piore Gold Medal and the 1992 Distinguished Service Award from the Computer Research Council.
Traub remained in close contact with CMU over the years and had planned to visit in October to join in the celebration of CSD's 50th anniversary.
"CMU is like China, in that when you visit China, if you come back 10 years later, it's an entirely new country and they have completely reinvented themselves," he said last year. "CMU is the same way. Every time I come back here, I'm thrilled by what's new."