Joseph Frederick Traub

Born June 24, 1932, Karlsruhe, Germany, Leader in the study of computational complexity.

Education: BS, City College of New York, 1954; PhD, applied mathematics, Columbia University, 1959.

Professional Experience. Mathematics Research Center, Computer Science Research Center, Bell Laboratories, Murray Hill, New Jersey, 1959-1971; head, Carnegie Mellon University, Computer Science Department, 1971-1979; Columbia University: Edwin Howard Armstrong professor and chairman, Computer Science Department, 1979 to 1986, professor of mathematics, 1979-1986; New York State Center for Computers and Information Systems: director, 1979-1986, chairman, Computer Science Department, 1987-1989, Edwin Howard Armstrong Professor, Computer Science Department, 1987-present; Princeton University: professor of computer science, 1986-1987, John von Neumann National Supercomputer Center, Consortium for Scientific Computing, president 1986-1987; chair, Computer Science and Telecommunications Board, 1986-1992.

Honors and Awards: member, National Academy of Engineering, 1985; fellow, American Association for the Advancement of Science, 1971; distinguished lecturer, MIT, February 1977; Edwin Howard Armstrong Memorial Lecture, Columbia University, 1980; First Annual BMAC Distinguished Lecture, Colorado State University, October 1982; University Lecture, Columbia University, February 1985; board of governors, New York Academy of Sciences, 1986-1989 (executive committee, 1987-1989); board of trustees, Charles Babbage Institute, 1989-present; Second Annual Charles Babbage Foundation Lecture, October 1989; chairman, Computer Science and Technology Board, National Research Council, 1986-1990; Lecture, Presidium, Academy of Sciences, Moscow, USSR, May 1990; chairman, Computer Science and Telecommunications Board, National Research Council, 1990-1992; First Prize, Ministry of Education, Poland, for the research monograph Information Based Complexity; distinguished lecture, UCLA, November 1991; distinguished lecture, UCSD, February 1991; Emanuel R. Piore Gold Medal, IEEE, 1991; Sherman Fairchild Distinguished Scholar, California Institute of Technology, 1991-1992; Distinguished Service Award, Computer Research Association, 1992; Distinguished Senior Scientist Award, Alexander von Humboldt Foundation, 1992; Lezioni Lincee, Accademia Nazionale dei Lincei, Rome, 1993; Computing Research Association Award for Service to Computing Research, 1993; fellow, ACM, 1994.

Starting in 1959, Traub pioneered research in what is now called information-based complexity, which studies the computational complexity of problems with partial and contaminated information. Such information is all that is available for many real-world problems. Information-based complexity is being used to solve the continuous problems typical of science, engineering, economics, and finance.

He was the founding chairman of the Computer Science Department at Columbia University from 1979 to 1989. From 1971 to 1979, he was head of the Computer Science Department at Carnegie Mellon University and led it from a critical period to eminence. He was founding chairman of the Computer Science and Telecommunications Board of the National Academy of Sciences. The board produces studies on matters of national concern related to computers and telecommunications.

He is the author or editor of eight books and some 100 journal articles. He is the founding editor of the Journal of Complexity, which began publication in 1985. Traub has served as adviser or consultant to the senior management of numerous organizations, including IBM, Hewlett-Packard, Schlumberger, Stanford University, IRIA (Paris), the Federal Judiciary Center, and the National Science Foundation.

BIBLIOGRAPHY

Significant Publications

Traub, J.F., Iterative Methods for the Solution of Equations, Prentice-Hall, New York, 1964; reissued Chelsea Publishing Company, 1982; Russian translation, MIR, 1985.

Traub, J.F., ed., Complexity of Sequential and Parallel Numerical Algorithms, Academic Press, New York, 1973.

Traub, J.F., ed., Analytic Computational Complexity, Academic Press, New York, 1975.

Traub, J.F., ed., Algorithms and Complexity: New Directions and Recent Results, Academic Press, New York, 1976.

Traub, J.F., and H. Wozniakowski, A General Theory of Optimal Algorithms, Academic Press, New York, 1983; Russian translation, MIR, 1980.

Traub, J.F., G. Wasilkowski, and H. Wozniakowski, Information, Uncertainty, Complexity, Addison-Wesley, New York, 1983; Russian translation, MIR, 1988.

Traub, J.F., ed., Cohabiting with Computers, William Kaufman, Inc., New York, 1985.

Traub, J.F., G. Wasilkowski, and H. Wozniakowski, Information-Based Complexity, Academic Press, New York, 1988.

UPDATES

Portrait replaced (MRW, 2013)

PDF version

Original content Copyright © 1995 by the Institute of Electrical and Electronics Engineers Inc.
New content Copyright © 2013-2015 by the IEEE Computer Society and the Institute of Electrical and Electronics Engineers Inc.
All rights reserved. This material may not be reproduced or redistributed without the express written permission of the copyright holder.