Joseph F Traub

Infobox_Scientist
name = Joseph Frederick Traub


caption =
birth_date = Birth date|1932|06|24
birth_place =
death_date =
death_place =
residence =
nationality =
field = Computer Science
work_institution = Columbia University
alma_mater =
doctoral_advisor = Henry Foley

Joseph Frederick Traub (born June 24, 1932), is a computer scientist. He is the Edwin Howard Armstrong Professor of Computer Science at Columbia University and External Professor at the Santa Fe Institute. He has held positions at Bell Laboratories, University of Washington, Carnegie Mellon, and Columbia, as well as sabbatical positions at Stanford, Berkeley, Princeton, California Institute of Technology, and Technical University, Munich. Traub is the author or editor of ten monographs and some 120 papers in computer science, mathematics, physics, finance, and economics. In 1959 he began his work on optimal iteration theory culminating in his 1964 monograph, which is still in print. Subsequently he pioneered work with [http://www.cs.columbia.edu/~henryk Henryk Woźniakowski] on computational complexity applied to continuous scientific problems (information-based complexity). He has collaborated in creating significant new algorithms including the Jenkins-Traub Algorithm for Polynomial Zeros, as well as the [http://portal.acm.org/citation.cfm?id=322068&coll=portal&dl=ACM Kung-Traub] , [http://portal.acm.org/citation.cfm?id=321810&dl=GUIDE&coll=GUIDE Shaw-Traub] , and [http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SMJCAT000009000001000054000001&idtype=cvips&gifs=yes Brent-Traub] algorithms. One of his current research areas is continuous quantum computing.

From 1971 to 1979 he headed the Computer Science Department at Carnegie Mellon and led it from a critical period to eminence (see [http://diva.library.cmu.edu/traub Joseph Traub digital archive at Carnegie Mellon] ). From 1979 to 1989 he was the founding Chair of the [http://www.cs.columbia.edu Computer Science Department at Columbia] . From 1986 to 1992 he served as founding Chair of the [http://www7.nationalacademies.org/CSTB/ Computer Science and Telecommunications Board, National Academies] and is again serving as Chair. Traub was founding Editor-in-Chief, [http://www.elsevier.com/wps/find/journaldescription.cws_home/622865/description#description Journal of Complexity] , in 1985 and continues in that capacity. Both his research and institution building work have had a major impact on the field of computer science.

Early career

He attended the Bronx High School of Science where he was captain and first board of the chess team. After graduating from City College of New York he entered Columbia in 1954 intending to take a PhD in physics. In 1955, on the advice of a fellow student, Traub visited the IBM Watson Research Lab at Columbia. At the time, this was one of the few places in the country where a student could gain access to computers. Traub found his proficiency for algorithmic thinking matched perfectly with computers. In 1957 he became a Watson Fellow through Columbia. His thesis was on computational quantum mechanics. His 1959 PhD is in applied mathematics since computer science degrees were not yet available. (Indeed, there was no Computer Science Department at Columbia until Traub was invited there in 1979 to start the Department.)

Career

In 1959 Traub joined the Research Division of Bell Laboratories in Murray Hill, NJ. One day a colleague asked him how to compute the solution of a certain problem. Traub could think of a number of ways to solve the problem. What was the optimal algorithm, that is, a method which would minimize the required computational resources? To his surprise, there was no theory of optimal algorithms. (The phrase computational complexity, which is the study of the minimal resources required to solve computational problems was not introduced until 1965.) Traub had the key insight that the optimal algorithm for solving a continuous problem depended on the available information. This was to eventually lead to the field of information-based complexity. The first area for which Traub applied his insight was the solution of nonlinear equations. This research led to the 1964 monograph [http://www.ams.org/bookstore?co1=AND&co2=AND&co3=AND&d=BOOK&f=G&fn=105&l=100&op1=AND&op2=AND&op3=AND&p=1&pg1=&pg2=&pg3=ALLF&r=3&s1=&s2=&s3=traub&subject=genint&u= Iterative Methods for the Solution of Equations] , which is still in print.

In 1966 he spent a sabbatical at Stanford where he met a student named Michael Jenkins. Together they created the Jenkins-Traub Algorithm for Polynomial Zeros. This algorithm is still one of the most widely used methods for this problem and is included in many textbooks.

In 1970 he became a professor at the University of Washington and in 1971 he became Head of the Carnegie Mellon Computer Science Department. The Department was quite small including Gordon Bell, Nico Haberman, Allen Newell, Raj Reddy, Herbert Simon, and William Wulf. Just prior to 1971 many faculty had left the Department to take positions elsewhere. Those professors who remained formed a core of world-class scientists recognized as leaders of the discipline. By 1978 the Department had grown to some 50 teaching and research faculty.(See [http://diva.library.cmu.edu/traub Joseph Traub digital archive at Carnegie Mellon] .)

One of Traub's PhD students was H. T. Kung, now a chaired professor at Harvard. They created the [http://portal.acm.org/citation.cfm?id=322068&coll=portal&dl=ACM Kung-Traub] algorithm for comparing the expansion of an algebraic function. They showed that computing the first $N$ terms was no harder than multiplying two $N$-th degree polynomials. This problem had been worked on by Isaac Newton who missed a key point.

In 1973 he invited [http://www.cs.columbia.edu/~henryk Henryk Woźniakowski] to visit CMU. They pioneered the field of information-based complexity, co-authoring three monographs and numerous papers. Woźniakowski is now a tenured professor at both Columbia and the University of Warsaw, Poland.

In 1978, while on sabbatical at Berkeley, he was recruited by Peter Likins to become founding Chairman of the [http://www.cs.columbia.edu Computer Science Department at Columbia] and Edwin Howard Armstrong Professor of Computer Science. He served as chair 1979-1989.

In 1980 he co-authored [http://www.jstor.org/view/00361445/di973512/97p0043n/0?frame=noframe&userID=[e-mail]/01cce4406700501b09cda&dpi=3&config=jstor A General Theory of Optimal Algorithms] , Academic Press, with Woźniakowski. This was the first research monograph on information-based complexity. [http://www.cs.uky.edu/~greg/ Greg Wasilkowski] joined Traub and Woźniakowski in two more monographs Information, Uncertainty, Complexity, Addison-Wesley, 1983, and Information-Based Complexity, Academic Press, 1988.

In 1985 Traub became founding Editor-in-Chief of the [http://www.elsevier.com/wps/find/journaldescription.cws_home/622865/description#description Journal of Complexity] . This was probably the first journal which had complexity in the sense of computational complexity in its title. Starting with two issues and 285 pages in 1985 the Journal now publishes six issues and nearly 1000 pages. Traub continues as Editor-in-Chief.

In 1986, he was asked by the National Academies to form a Computer Science Board. The original name of the Board was the Computer Science and Technology Board (CSTB). Several years later CSTB was asked to also be responsible for telecommunications so it was renamed the [http://www.cstb.org Computer Science and Telecommunications Board] , preserving the abbreviation CSTB. The Board deals with critical national issues in computer science and telecommunications. Traub served as founding chair 1986-1992 and is again serving as chair starting in 2005.

In 1990 Traub taught in the summer school of the [http://www.santafe.edu Santa Fe Institute] (SFI). He has since played a variety of roles at SFI. In the nineties he organized a series of Workshops on Limits to Scientific Knowledge funded by the Alfred P. Sloan Foundation. The goal was to enrich science in the same way that the work of Gŏdel and Turing on the limits of mathematics enriched that field. There were a series of Workshops on limits in various disciplines: physics, economics, and geophysics. Currently he is an External Professor at SFI.

Starting in 1991 Traub has been co-organizer of an international Seminar on "Continuous Algorithms and Complexity" at [http://www.dagstuhl.de Schloss Dagstuhl] , Germany. The ninth Seminar was held in September 2006. Many of the Seminar talks are on information-based complexity and more recently on continuous quantum computing.

Traub was invited by the Accademia Nazionale dei Lincee in Rome, Italy, to present the 1993 Lezione Lincee. He chose to give the cycle of six lectures at the Scuola Normale in Pisa. He invited Arthur Werschulz to join him in publishing the lectures. The lectures appeared in expanded form in [http://www.amazon.com/dp/0521485061/ Complexity and Information] , Cambridge University Press, 1998.

In 1994 he asked a PhD student, Spassimir Paskov, to compare the Monte Carlo method (MC) with the Quasi-Monte Carlo method (QMC) when calculating a collateralized mortgage obligation (CMO) Traub had obtained from Goldman Sachs. This involved the numerical approximation of a number of integrals in $360$ dimensions. To the surprise of the research group Paskov reported that QMC always beat MC for this problem. People in finance had always used MC for such problems and the experts in number theory believed QMC should not be used for integrals of dimension greater than $12$. Paskov and Traub reported their results to a number of Wall Street firms to considerable initial skepticism. They first published the results in Paskov and Traub [http://www.cs.columbia.edu/~traub/cucs-030-96.pdf Faster Evaluation of Financial Derivatives] , Journal of Portfolio Management 22, 1995, 113-120. The theory and software was greatly improved by [http://www.cs.columbia.edu/~ap Anargyros Papageorgiou] . Today QMC is widely used in the financial sector to value financial derivatives. QMC is not a panacea for all high dimensional integrals. Research is continuing on the characterization of problems for which QMC is superior to MC.

In 1999 Traub received the Mayor's medal for Science and Technology. Decisions regarding this award are made by the New York Academy of Sciences. The medal was awarded by Mayor Rudy Giuliani in a ceremony in Gracie Mansion, the home of New York City's mayor.

Moore's law is an empirical observation that the number of features on a chip doubles roughly every 18 months. This has held since the early 60s and is responsible for the computer and telecommunications revolution. It is widely believed that Moore's law will cease to hold in 10-15 years using silicon technology. There is therefore interest in creating new technologies. One candidate is quantum computing. That is building a computer using the principles of quantum mechanics. Traub and his colleagues decided to work on continuous quantum computing. The motivation is that most problems in physical science, engineering, and mathematical finance have continuous mathematical models.

In 2005 Traub donated some 100 boxes of archival material to the [http://diva.library.cmu.edu Carnegie Mellon University Library] . This collection is being digitized.

Talk given by J. F. Traub for 25th Anniversary of Columbia’s Computer Science Department

Before the establishment of the Computer Science Department in 1979, there were computer science efforts in the Mathematical Statistics Department in Arts and Sciences, and in the Electrical Engineering Department in the School of Engineering. In the academic year 1978-79 Peter Likins, the Dean of the School of Engineering (now President of the University of Arizona) persuaded the University to eliminate both these efforts and to create a Computer Science Department. The creation of the new Department was strongly supported by Columbia's central administration.

At the time I headed the Computer Science Department at Carnegie Mellon University, universally ranked together with Stanford and MIT as one of the premier departments in the world. Peter approached me to be the founding chair of the new department at Columbia. I agreed to come under certain conditions which included:
* a new building for the Department
* faculty positions - Likins started the Department with thirteen slots and said "don't ask for any more".
* a teaching load competitive with leading computer science departments at private universities

Likins agreed to all requests and I came to Columbia University on July 1, 1979. The new Department had four tenured professors (Theodore Baskow, Jonathan Gross, Stephen Unger and myself). The decision was made to recruit the best possible new PhDs , as well as a few outstanding senior faculty, which required that the existing non-tenured faculty had to be asked to leave.

The following people, who are now all senior faculty joined the Department in the early years:

*Peter Allen
*Steven Feiner
*Zvi Galil
*Gail Kaiser
*John Kender
*Kathy McKeown
*Sal Stolfo
*Henryk Wozniakowski
*Yechiam Yemini

It was decided to import some of the Carnegie-Mellon principles which included:a strong commitment to research and teaching quality
*faculty collegiality
*treating students as colleagues
*a Black Friday meeting every semester to evaluate all PhD students

Many people have asked me why this evaluation meeting is called Black Friday, especially when at Columbia its usually been held on Thursday. The reason is shrouded in the fog of computer history but I'd like to share it with you.We have to return to CMU in 1971 where I met weekly with a faculty-student committee which was revising the PhD program. One Saturday night my wife, Pamela, and I were watching Chilly Billy's Thriller Theatre on TV and we saw a Grade B horror movie about the dead returning every hundred years called Black Sunday. The following week the Committee decided to create a twice-a-year meeting to monitor the progress of our PhD students and scheduled the first meeting on a Friday. When I notified the CS Department, I casually referred to this as the Black Friday meeting. The name stuck and when I brought the idea to Columbia, we continued to use it.

Much had to be accomplished in the creation of the new department. Peter Likins was marvelously supportive at all times. Here are some of the things we had to do.

The faculty had to be built almost from scratch. One of the characteristics of computer science, as opposed to many other disciplines, is that there are many more available positions than absolutely top people to fill them. It was true at Carnegie in 1971; it's true today. That is healthy for the discipline but makes it difficult for faculty recruiting. For every appointment, the new Department had to compete with top academic departments and top research labs. Nonetheless, superb new faculty were hired.

At the same time there was huge student demand for courses. Two thousand students took courses in the first year, 2600 the next year, and 4200 a few years later. There were as many as 200 students per course. We were trying to hire the top young PhDs and yet they had to teach classes of 200 students. The Department started to hire lecturers to help with teaching , especially for the beginning courses. We hired lecturers who loved to teach and who interacted well with undergraduates.

The Department started Bachelor's, Master's and PhD programs. It taught computer science to all of Columbia University so there were majors from the Engineering College, Columbia College, Barnard, General Studies and the Graduate School. Jonathan Gross served as Vice-Chair. Among his responsibilities were creation of the curricula and oversight of the various Bachelor's programs.

Obtaining funds was crucial to building Departmental research. In the first year, IBM gave the Department a six hundred thousand dollar gift. Pivotal to giving the Department a big push was a very large contract from DARPA, the Defense Advanced Research Projects Agency. DARPA monies had been critical to the building of the "big three": Carnegie-Mellon, MIT and Stanford. Bob Kahn, then the Director of DARPA's Information Processing Techniques Office, decided to give major funding to two more Departments, Berkeley and Columbia. The DARPA funding was crucial to the Department's early years. In addition to providing funds for research staff, research equipment, and PhD students, it provided funds for equipment and staffing of a computer facility. Furthermore, it gave the Department a vital connection to the Arpanet.

New York City was a major plus in recruiting faculty and students but could sometimes make matters more complicated. The Arpanet connection provides a good example. In 1979 Columbia did not have an Arpanet connection. Parenthetically, although its hard to believe today, the entire Engineering school's only computer was a PDP11/45. How to connect to the Arpanet? Connecting via NYU would have been the obvious solution but the density of wires and pipes in midtown made that unfeasible and we had to come up with a more complicated solution.

As I mentioned earlier, there was a University commitment to give the Department a new building. The boutique firm of Kliment and Halsband was chosen as architects. The building won the AIA Honors Award, which, for an architect, is the equivalent of an Oscar or a Pulitzer Prize. To celebrate the new building, a convocation was held in 1983. There were talks by distinguished leaders in computing and Herbert Simon received an honorary doctorate.

In 1979 Columbia University was fairly late in starting a Computer Science Department. The Department felt it was important to demonstrate to the University the centrality of the discipline. One of the ways this was accomplished was through the “Columbia University Lectures in Computer Science". The distinguished and diverse speakers included sociologist Sherry Turkle, computer animation pioneer John Whitney, and Douglas Hofstadter, author of the Pulitzer Prize winning book, "Goedel, Escher, Bach". The lectures always drew large audiences.

In 1984 the Department was five years old. It had twenty four faculty positions (Peter Likins' limit of thirteen had long been passed). The PhD program had 60 students and there were 6 to 7 million dollars a year in outside support. A state-wide competition led to Columbia's designation as the New York State Center for Computers and Information Systems. IBM gave a generous gift of 4 million dollars in money and equipment. The first stage in the building of the Computer Science Department had been completed.

Personal

He has two daughters, Claudia Traub-Cooper and Hillary Spector. He lives in Manhattan and Santa Fe with his wife, noted author [http://www.pamelamccorduck.com Pamela McCorduck] whose books include "Machines Who think, The Fifth Generation, The Universal Machine, Aaron's Code" and "The Futures of Women".

Selected honors and distinctions

*Member, National Academy of Engineering, 1985
*Founding Chair, [http://www7.nationalacademies.org/CSTB/ Computer Science and Telecommunications Board, National Academies] , 1986-92, 2005-
*Sherman Fairchild Distinguished Scholar, California Institute of Technology, 1991-2
*Distinguished Senior Scientist Award, [http://www.humboldt-foundation.de Alexander von Humboldt Foundation] , 1992, 1998
*1993 Lezione Lincee, Accademia Nazionale dei Lincei, Rome, Italy
*Lecture, Presidium, Academy of Sciences, Moscow, USSR 1990
*Member, Scientific Council, Institut en Recherche en Informatique, Paris, France, 1976-1980
*First Prize, Ministry of Education, Poland, for the research monograph "Information-Based Complexity", 1989
*1991 Emanuel R. Piore Medal, IEEE
*1992 Distinguished Service Award, Computing Research Association
*Board of Governors, New York Academy of Sciences, 1986-9 (Executive Committee 1987-89)
*Fellow: American Association for the Advancement of Science, 1971; ACM 1994; New York Academy of Sciences, 1999
*1999 New York City Mayor's Award for Excellence in Science and Technology
*Search Committee, President, National Academy of Engineering 1994-5
*Festschrift for Joseph F. Traub, Academic Press, 1993
*Festschrift for Joseph F. Traub, Elsevier, 2004
*Honorary Doctorate of Science, University of Central Florida, 2001
*Founding Editor-in-Chief, [http://www.elsevier.com/wps/find/journaldescription.cws_home/622865/description#description Journal of Complexity] , 1985-

Selected puplications

Selected monographs

*"Iterative Methods for the Solution of Equations", Prentice Hall, 1964. Reissued Chelsea Pulishing Company, 1982; Russian translation MIR, 1985; Reissued Amarican Mathematical Society, 1998.
*"Algorithms and Complexity: New Direcions and Recent Results", (editor) Academic Press, 1976.
*"Information-Based Complexity", Academic Press, 1988 (with G. Wasilkowski and H. Woźniakowski).
*"Complexity and Information", Cambridge University Press, 1998 (with A. G. Werschulz); Japanese translation, 2000.

Selected papers

*"Variational Calculations of the $2^3P$ State of Helium", Phys. Rev. 116, 1959, 914-919.
*"The Future of Scientific Journals", Science 158, 1966, 1153-1159 (with W. S. Brown and J. R. Pierce).
*"A Three-Stage Variable-Shift Iteration for Polynomial Zeros and Its Relation to Generalized Rayleigh Iteration", Numerische mathematik 14, 1970, 252-263 (with M. A. Jenkins).
*"Computational Complexity of Iterative Processes", SIAM Journal on Computing 1, 1972, 167-179.
*"Parallel Algorithms and Parallel Computational Complexity", Proceedings IFIP Congress, 1974, 685-687.
*"Convergence and Complexity of Newton Iteration for Operator Equations", Journal of the ACM 26, 1979, 250-258 (with H. Woźniakowski).
*"All Algebraic Functions Can Be Computed Fast", Journal of the ACM 25, 1978, 245-260 (with H. T. Kung).
*"On the Complexity of Composition and Generalized Composition of Power Series, SIAM Journal on Computing 9, 1980, 54-66 (with R. Brent).
*"Complexity of Linear Programming", Operations Research Letters 1, 1982, 59-62 (with H. Woźniakowski).
*"Information-Based Complexity", Nature 327, July, 1987, 29-33 (with E. Packel).
*"The Monte Carlo Algorithm with a Pseudo-Random Number Generator", Mathematics of Computation 58, 199, 303-339 (with H. Woźniakowski).
*"Breaking Intractability", Scientific American, January, 1994, 102-107 (with H. Woźniakowski). Translated into German, Italian, Japanese and Polish.
*"Linear Ill-Posed Problems are Solvable on the Average for All Gaussian Measures", Math Intelligencer 16, 1994, 42-48 (with A. G. Werschulz).
*"Faster Evaluation of Financial Derivatives", Journal of Portfolio Management 22, 1995, 113-120 (with S. Paskov).
*"A Continuous Model of Computation", Physics Today, May, 1999, 39-43.
*"No Curse of Dimensionality for Contraction Fixed points in the Worst Case", Econometrics, Vol. 70, No. 1, January, 2002, 285-329 (with J. Rust and H. Woźniakowski).
*"Path Integration on a Quantum Computer", Quantum Information Processing, 2003, 365-388 (with H. Woźniakowski).

External links

* [http://www.cs.columbia.edu/~traub Joseph Traub's Columbia homepage]
* [http://diva.library.cmu.edu/traub Joseph Traub digital archive at Carnegie Mellon]
* [http://www7.nationalacademies.org/CSTB/ Computer Science and Telecommunications Board, National Academies]
*Research monograph [http://www.amazon.com/dp/0521485061/ Complexity and Information]
* [http://www.cbi.umn.edu/oh/display.phtml?id=38 Charles Babbage Institute Oral History of Joseph Traub]
* [http://history.siam.org/oralhistories/traub.htm SIAM Oral History]
* [http://www.elsevier.com/wps/find/journaldescription.cws_home/622865/description#description Homepage of Journal of Complexity]
* [http://www.cs.columbia.edu/~henryk Henryk Woźniakowski Columbia homepage]
* [http://www.cs.columbia.edu/~ap Anargyros Papageorgiou Columbia homepage]
* [http://www.pamelamccorduck.com Pamela McCorduck homepage]
* [http://math.fullerton.edu/mathews/n2003/jenkinstraub/JenkinsTraubBib/Links/JenkinsTraubBib_lnk_2.html Publications referring to the Jenkins-Traub method]
* [http://www.dagstuhl.de Homepage of Schloss Dagstuhl]
* [http://www.cs.columbia.edu/~traub/SCS_9_19.wmv CMU Distinguished Lecture Video]
* [http://www.cs50.cs.cmu.edu/inside.php?page_id=42 CMU 50th Anniversary Video]
*List of computer scientists