Wikipedia

Joseph F. Traub

(Redirected from Joseph Traub)

Joseph Frederick Traub (June 24, 1932 – August 24, 2015) was an American computer scientist. He was the Edwin Howard Armstrong Professor of Computer Science at Columbia University and External Professor at the Santa Fe Institute. He held positions at Bell Laboratories, University of Washington, Carnegie Mellon, and Columbia, as well as sabbatical positions at Stanford,[3] Berkeley, Princeton, California Institute of Technology, and Technical University, Munich.[4]

Joseph F. Traub
Born
Joseph Frederick Traub

(1932-06-24)June 24, 1932
Karlsruhe, Weimar Germany[1]
DiedAugust 24, 2015(2015-08-24) (aged 83)
Santa Fe, New Mexico, U.S.[2]
NationalityAmerican
Alma materCity College of New York (B.S., 1954)
Columbia University (Ph.D., Applied Mathematics, 1959)
SpousePamela McCorduck
Scientific career
FieldsComputer Science
InstitutionsColumbia University
Thesis Variational Calculations on the Triplet-2S and Triplet-2P States of Helium  (1959)
Doctoral advisorHenry M. Foley
Doctoral students

Traub was the author or editor of ten monographs and some 120 papers in computer science, mathematics, physics, finance, and economics.[4] In 1959 he began his work on optimal iteration theory culminating in his 1964 monograph, Iterative Methods for the Solution of Equations. Subsequently, he pioneered work with Henryk Woźniakowski on computational complexity applied to continuous scientific problems (information-based complexity). He collaborated in creating significant new algorithms including the Jenkins-Traub Algorithm for Polynomial Zeros, as well as the Shaw-Traub,[2][5] Kung-Traub,[6] and Brent-Traub algorithms. One of his research areas was continuous quantum computing.[7] As of November 10, 2015, his works have been cited 8500 times, and he has an h-index of 35.[8]

From 1971 to 1979 Traub headed the Computer Science Department at Carnegie Mellon during a critical period. From 1979 to 1989 he was the founding Chair of the Computer Science Department at Columbia. From 1986 to 1992 he served as founding Chair of the Computer Science and Telecommunications Board, National Academies and held the post again 2005–2009.[9] Traub was founding editor of the Annual Review of Computer Science (1986–1990)[10] and Editor-in-Chief of the Journal of Complexity (1985–2015).[11] Both his research and institution building work have had a major impact on the field of computer science.[4]

Early career

edit

Traub 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.)[12][4]

Career

edit

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, Iterative Methods for the Solution of Equations.[12][6] which is still in print.[13]

In 1966 Traub spent a sabbatical year at Stanford University where he met a student named Michael Jenkins. Together they developed the Jenkins-Traub Algorithm for Polynomial Zeros, which was published as Jenkins' Ph.D. thesis. This algorithm is still one of the most widely used methods for this problem and is included in many textbooks.[14][1]

In 1970 Traub became a professor at the University of Washington and in 1971 he became Head of the Carnegie Mellon Computer Science Department.[15] The Department was quite small but still included "giants" such as Allen Newell and Herbert A. Simon. By 1978, under Traub's leadership, the Department had grown to some 50 teaching and research faculty.[16]

One of Traub's PhD students was H. T. Kung, now a chaired professor at Harvard. They created the Kung-Traub algorithm for computing the expansion of an algebraic function. They showed that computing the first   terms was no harder than multiplying two  -th degree polynomials.[6][17][18]

In 1973 Traub invited Henryk Woźniakowski to visit CMU.[1] They pioneered the field of information-based complexity, co-authoring three monographs and numerous papers. Woźniakowski became a professor at both Columbia and the University of Warsaw, Poland.[19]

In 1978, while on sabbatical at Berkeley, he was recruited by Peter Likins to become founding Chairman of the Computer Science Department at Columbia and Edwin Howard Armstrong Professor of Computer Science. He served as chair 1979–1989.[20]

In 1980 he co-authored A General Theory of Optimal Algorithms, with Woźniakowski. This was the first research monograph on information-based complexity.[21] Greg Wasilkowski joined Traub and Woźniakowski in two more monographs Information, Uncertainty, Complexity, Addison-Wesley, 1983,[22] and Information-Based Complexity, Academic Press, 1988.[23]

In 1985 Traub became founding Editor-in-Chief of the Journal of Complexity.[2][24] This was probably the first journal which had complexity in the sense of computational complexity in its title.[25]

In 1986, Traub 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 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 held the post again 2005–2009.[12]

In 1990 Traub taught in the summer school of the Santa Fe Institute (SFI). He has since played a variety of roles at SFI.[2] 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.[26]

Starting in 1991 Traub was co-organizer of an international Seminar on "Continuous Algorithms and Complexity" at Schloss Dagstuhl, Germany. Many of the Seminar talks are on information-based complexity and more recently on continuous quantum computing.[27]

Traub was invited by the Accademia Nazionale dei Lincee in Rome, Italy, to present the 1993 Lezione Lincee.[12] 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 as Complexity and Information, Cambridge University Press, 1998.[28][29]

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 1995.[30][31][32] The theory and software was greatly improved by 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.[33] 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.[4]

Traub and his colleagues have also worked on continuous quantum computing. 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. The motivation is that most problems in physical science, engineering, and mathematical finance have continuous mathematical models.[34]

In 2005 Traub donated archival material to the Carnegie Mellon University Library. This collection is being digitized.[4]

Patents on algorithms and software

edit

The U.S. patents US5940810 and US0605837 were issued to Traub et al. for the FinDer Software System and were assigned to Columbia University. These patents cover an application of a well known technique (low discrepancy sequences) to a well known problem (valuation of securities).[35]

Personal life

edit

Traub had two daughters, Claudia Traub-Cooper and Hillary Spector. He lived in Manhattan and Santa Fe with his wife, author Pamela McCorduck. He often opined on current events by writing to the New York Times, which frequently published his comments.[36][37]

Selected honors and distinctions

edit

Selected publications

edit

Selected monographs

edit
  • Iterative Methods for the Solution of Equations, Prentice Hall, 1964. Reissued Chelsea Publishing Company, 1982; Russian translation MIR, 1985; reissued American Mathematical Society, 1998.
  • Algorithms and Complexity: New Directions 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

edit
  • Variational Calculations of the   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).

References

edit
  1. ^ a b c Gelenbe, Erol (2011). "An Interview with Joseph F. Traub". Ubiquity. 2011 (February): 1–15. doi:10.1145/1940721.1941856. S2CID 34530233.
  2. ^ a b c d e Crane, Linda (August 25, 2015). "In Memoriam: Joseph F. Traub | Department of Computer Science, Columbia University". Columbia Engineering. Retrieved 4 April 2023.
  3. ^ "Biography | Joseph F. Traub Collection". Carnegie Mellon University, University Libraries. Retrieved 4 April 2023.
  4. ^ a b c d e f g "Joseph Traub". Carnegie Mellon University Digital Collections. Retrieved 4 April 2023.
  5. ^ Shaw, Mary; Traub, J. F. (1 January 1974). "On the Number of Multiplications for the Evaluation of a Polynomial and Some of Its Derivatives". Journal of the ACM. 21: 161–167. doi:10.1145/321796.321810. S2CID 10595083.
  6. ^ a b c Petković, Miodrag S.; Neta, Beny; Petković, Ljiljana D.; Džunić, Jovana (January 2014). "Multipoint methods for solving nonlinear equations: A survey" (PDF). Applied Mathematics and Computation. 226: 635–660. doi:10.1016/j.amc.2013.10.072. hdl:10945/39425. S2CID 2499424. Retrieved 4 April 2023.
  7. ^ Novak, Erich (2009). "Henryk Wozniakowski and the Complexity of Continuous Problems". Essays on the complexity of continuous problems (PDF). Zürich, Switzerland: European Mathematical Society. ISBN 978-3-03719-069-2. Retrieved 4 April 2023.
  8. ^ "Google Scholar Citation Record for J.F. Traub".
  9. ^ a b c "Computer Pioneers - Joseph Frederick Traub". Institute of Electrical and Electronics Engineers. Retrieved 4 April 2023.
  10. ^ Kaufmann, William (June 1986). "Preface". Annual Review of Computer Science. 1 (1): annurev.cs.1.111406.100001. doi:10.1146/annurev.cs.1.111406.100001. Retrieved 13 September 2021.
  11. ^ Lohr, Steve (26 August 2015). "Joseph F. Traub, 83, Dies; Early Advocate for Computer Science". The New York Times. Retrieved 4 April 2023.
  12. ^ a b c d e National Academy of Engineering (2022). "Joseph F. Traub 1932–2015". Memorial tributes. Vol. 24. Washington, DC: The National Academies Press. ISBN 978-0-309-28717-3. Retrieved 4 April 2023.
  13. ^ "Iterative Methods for the Solution of Equations". American Mathematical Society. Retrieved 15 November 2021.
  14. ^ Binner, David (6 March 2008). "Polynomial Root-finding with the Jenkins-Traub Algorithm". Math ∞ Blog. Retrieved 4 April 2023.
  15. ^ Lazowska, Ed (August 30, 2015). "Remembering Joe Traub, 1932-2015". Allen School News. Retrieved 4 April 2023.
  16. ^ Spice, Byron (August 27, 2015). "In Memoriam: Joseph F. Traub". Carnegie Mellon School of Computer Science. Retrieved 4 April 2023.
  17. ^ Meersman, Robert (1975). "A survey of techniques in applied computational complexity c*)". Journal of Computational and Applied Mathematics. I (1): 39–46. doi:10.1016/0771-050X(75)90005-4.
  18. ^ Kung, H. T.; Traub, J. F. (1 April 1978). "All Algebraic Functions Can Be Computed Fast". Journal of the ACM. 25 (2): 245–260. doi:10.1145/322063.322068. S2CID 5933519. Retrieved 15 November 2021.
  19. ^ "Journal of Complexity". Elsevier. Retrieved 4 April 2023.
  20. ^ McCaughey, Robert A. (2014). A Lever Long Enough : a History of Columbia's School of Engineering and Applied Science Since 1864. New York: Columbia University Press. doi:10.7312/columbia/9780231166881.003.0007. ISBN 9780231166881.
  21. ^ Parlett, Beresford N. (1992). "Some basic information on information-based complexity theory" (PDF). Bulletin (New Series) of the American Mathematical Society. 26 (1): 3–28. arXiv:math/9201266. doi:10.1090/S0273-0979-1992-00239-2. S2CID 3077531.
  22. ^ Shub, Michael (September 1987). "Information, Uncertainty, Complexity (J. F. Traub, G. W. Wasilkowski and H. Woźniakowski)". SIAM Review. 29 (3): 495–497. doi:10.1137/1029099. ISSN 0036-1445.
  23. ^ Kon, Mark A. (October 1989). "Review: J. F. Traub, G. W. Wasilkowski and H. Woźniakowski, Information-based complexity". Bulletin (New Series) of the American Mathematical Society. 21 (2): 332–339. doi:10.1090/S0273-0979-1989-15851-5. ISSN 0273-0979. Retrieved 4 April 2023.
  24. ^ "In honor of the late founding Editor-in-Chief of the Journal of Complexity: The Joseph F. Traub fellowship has been established. - News - Journal of Complexity - Journal - Elsevier". Elsevier. Retrieved 4 April 2023.
  25. ^ Traub, J. F. (1985). "Complexity of Approximately Solved Problems" (PDF). Journal of Complexity. 1: 3–10. doi:10.1016/0885-064X(85)90019-6.
  26. ^ Hut, Piet; Ruelle, David; Traub, Joseph (1998). "Varieties of Limits to Scientific Knowledge | Santa Fe Institute" (PDF). Complexity. 3 (6). John Wiley & Sons. Inc. doi:10.1002/(SICI)1099-0526(199807/08)3:6<33::AID-CPLX5>3.0.CO;2-L. Retrieved 4 April 2023.
  27. ^ Dagstuhl-Seminar-Report; 11 15-19.4.1991 (9116) (PDF). IBFI GmbH. 1991.
  28. ^ Kon, Mark A. (December 21, 1999). "Complexity and information, by J. F. Traub and A. G. Werschulz, Cambridge University Press, Cambridge, 1998, xii + 139 pp., $19.95, ISBN 0-521-48506-1 (paperback)" (PDF). Bulletin (New Series) of the American Mathematical Society. 37 (2): 199–204. doi:10.1090/S0273-0979-99-00859-9. Retrieved 4 April 2023.
  29. ^ Casti, John L. (17 April 1999). "Mission impossible". New Scientist. Retrieved 4 April 2023.
  30. ^ "Artful financial computation via deterministic sampling | Santa Fe Institute". www.santafe.edu. 7 July 2011. Retrieved 4 April 2023.
  31. ^ Hayes, Brian (2011). "Quasirandom Ramblings" (PDF). American Scientist. 99 (4): 282–287. doi:10.1511/2011.91.282.
  32. ^ Paskov, Spassimir H.; Traub, Joseph F. (31 October 1995). "Faster Valuation of Financial Derivatives". The Journal of Portfolio Management. 22 (1): 113–123. doi:10.3905/jpm.1995.409541. ISSN 0095-4918. S2CID 17278384. Retrieved 4 April 2023.
  33. ^ Papageorgiou, A.; Traub, J.F. (1996). "Beating Monte Carlo" (PDF). Risk. 9 (6): 63–65.
  34. ^ Shandor, John (5 October 2001). "Killer apps for quantum computers". HPCwire. Retrieved 4 April 2023.
  35. ^ Papageorgiou, A. "Patent information". www.cs.columbia.edu. Retrieved 22 March 2018.
  36. ^ Traub, Joseph (August 3, 2004). "The Terror Alert: New Tension in a Jittery Nation". The New York Times.
  37. ^ Traub, Joseph (August 17, 2004). "Florida and the Wrath of Charley". The New York Times.
  38. ^ "IEEE Emanuel R. Piore Award Recipients" (PDF). IEEE. Archived from the original (PDF) on November 24, 2010. Retrieved March 20, 2021.
  39. ^ "Honorary Members and Academy Fellows". New York Academy of Sciences. 12 April 2017. Retrieved 4 April 2023.
  40. ^ "Historic Fellows". American Association for the Advancement of Science (aaas.org). (Search on last_name="Traub".)
  41. ^ List of Fellows of the American Mathematical Society, retrieved 2013-08-27.
edit
Retrieved from "https://en.wikipedia.org/w/index.php?title=Joseph_F._Traub&oldid=1258534965"