Joseph F Traub
Encyclopedia
Joseph Frederick Traub 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 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 Kung-Traub, Shaw-Traub, and 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 Joseph Traub digital archive at Carnegie Mellon). 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 is again serving as Chair. Traub was founding Editor-in-Chief, 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
.
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.)
, 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, 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 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 Kung-Traub algorithm for comparing the expansion of an algebraic function. They showed that computing the first
terms was no harder than multiplying two 
-th degree polynomials. This problem had been worked on by Isaac Newton who missed a key point.
In 1973 he invited 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 Computer Science Department at Columbia and Edwin Howard Armstrong Professor of Computer Science. He served as chair 1979-1989.
In 1980 he co-authored A General Theory of Optimal Algorithms, Academic Press, with Woźniakowski. This was the first research monograph on information-based complexity. 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 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 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 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 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 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
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
. 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 Faster Evaluation of Financial Derivatives, Journal of Portfolio Management 22, 1995, 113-120. 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. 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 Carnegie Mellon University Library. This collection is being digitized.
whose books include Machines Who think, The Fifth Generation, The Universal Machine, Aaron's Code and The Futures of Women.
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
. He is the Edwin Howard Armstrong Professor of Computer Science at Columbia University
Columbia University
Columbia University in the City of New York is a private, Ivy League university in Manhattan, New York City. Columbia is the oldest institution of higher learning in the state of New York, the fifth oldest in the United States, and one of the country's nine Colonial Colleges founded before the...
and External Professor at the Santa Fe Institute
Santa Fe Institute
The Santa Fe Institute is an independent, nonprofit theoretical research institute located in Santa Fe and dedicated to the multidisciplinary study of the fundamental principles of complex adaptive systems, including physical, computational, biological, and social systems.The Institute houses a...
. He has held positions at Bell Laboratories, University of Washington
University of Washington
University of Washington is a public research university, founded in 1861 in Seattle, Washington, United States. The UW is the largest university in the Northwest and the oldest public university on the West Coast. The university has three campuses, with its largest campus in the University...
, Carnegie Mellon, and Columbia, as well as sabbatical positions at Stanford, Berkeley, Princeton
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
, California Institute of Technology
California Institute of Technology
The California Institute of Technology is a private research university located in Pasadena, California, United States. Caltech has six academic divisions with strong emphases on science and engineering...
, and Technical University, Munich
Technical University of Munich
The Technische Universität München is a research university with campuses in Munich, Garching, and Weihenstephan...
. 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 Henryk Woźniakowski on computational complexity applied to continuous scientific problems (information-based complexity
Information-based complexity
Information-based complexity studies optimal algorithms and computational complexity for the continuous problems which arise in physical science, economics, engineering, and mathematical finance...
). He has collaborated in creating significant new algorithms including the Jenkins-Traub Algorithm for Polynomial Zeros, as well as the Kung-Traub, Shaw-Traub, and 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
Carnegie Mellon School of Computer Science
The School of Computer Science at Carnegie Mellon University in Pittsburgh, Pennsylvania, USA is a leading private school for computer science established in 1965. It has been consistently ranked among the top computer science programs over the decades. U.S...
and led it from a critical period to eminence (see Joseph Traub digital archive at Carnegie Mellon). 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 is again serving as Chair. Traub was founding Editor-in-Chief, 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
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
.
Early career
He attended the Bronx High School of ScienceBronx High School of Science
The Bronx High School of Science is a specialized New York City public high school often considered the premier science magnet school in the United States. Founded in 1938, it is now located in the Bedford Park section of the Bronx...
where he was captain and first board of the chess team. After graduating from City College of New York
City College of New York
The City College of the City University of New York is a senior college of the City University of New York , in New York City. It is also the oldest of the City University's twenty-three institutions of higher learning...
he entered Columbia
Columbia University
Columbia University in the City of New York is a private, Ivy League university in Manhattan, New York City. Columbia is the oldest institution of higher learning in the state of New York, the fifth oldest in the United States, and one of the country's nine Colonial Colleges founded before the...
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
Thomas J. Watson Research Center
The Thomas J. Watson Research Center is the headquarters for the IBM Research Division.The center is on three sites, with the main laboratory in Yorktown Heights, New York, 38 miles north of New York City, a building in Hawthorne, New York, and offices in Cambridge, Massachusetts.- Overview :The...
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
Quantum mechanics
Quantum mechanics, also known as quantum physics or quantum theory, is a branch of physics providing a mathematical description of much of the dual particle-like and wave-like behavior and interactions of energy and matter. It departs from classical mechanics primarily at the atomic and subatomic...
. His 1959 PhD is in applied mathematics
Applied mathematics
Applied mathematics is a branch of mathematics that concerns itself with mathematical methods that are typically used in science, engineering, business, and industry. Thus, "applied mathematics" is a mathematical science with specialized knowledge...
since computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
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 complexityComputational Complexity
Computational Complexity may refer to:*Computational complexity theory*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
Information-based complexity
Information-based complexity studies optimal algorithms and computational complexity for the continuous problems which arise in physical science, economics, engineering, and mathematical finance...
. 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, 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
University of Washington
University of Washington is a public research university, founded in 1861 in Seattle, Washington, United States. The UW is the largest university in the Northwest and the oldest public university on the West Coast. The university has three campuses, with its largest campus in the University...
and in 1971 he became Head of the Carnegie Mellon Computer Science Department
Carnegie Mellon School of Computer Science
The School of Computer Science at Carnegie Mellon University in Pittsburgh, Pennsylvania, USA is a leading private school for computer science established in 1965. It has been consistently ranked among the top computer science programs over the decades. U.S...
. The Department was quite small including Gordon Bell
Gordon Bell
C. Gordon Bell is an American computer engineer and manager. An early employee of Digital Equipment Corporation 1960–1966, Bell designed several of their PDP machines and later became Vice President of Engineering 1972-1983, overseeing the development of the VAX...
, Nico Haberman, Allen Newell
Allen Newell
Allen Newell was a researcher in computer science and cognitive psychology at the RAND corporation and at Carnegie Mellon University’s School of Computer Science, Tepper School of Business, and Department of Psychology...
, Raj Reddy, Herbert Simon
Herbert Simon
Herbert Alexander Simon was an American political scientist, economist, sociologist, and psychologist, and professor—most notably at Carnegie Mellon University—whose research ranged across the fields of cognitive psychology, cognitive science, computer science, public administration, economics,...
, and William Wulf
William Wulf
William Allan Wulf is a computer scientist notable for his work in programming languages and compilers.Born in Chicago, Illinois, he attended the University of Illinois, receiving a BS in Engineering Physics and an MS in Electrical Engineering, then achieved the first Ph.D. in Computer Science...
. 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 Joseph Traub digital archive at Carnegie Mellon.)
One of Traub's PhD students was H. T. Kung
H. T. Kung
H. T. Kung is a computer scientist. His current research is primarily in the area of communications networks and network security, but his interests have been broad-ranging, including computational complexity theory, database theory, VLSI design, and parallel computing.Kung received his bachelor...
, now a chaired professor at Harvard. They created the Kung-Traub algorithm for comparing the expansion of an algebraic function. They showed that computing the first
terms was no harder than multiplying two -th degree polynomials. This problem had been worked on by Isaac Newton who missed a key point.In 1973 he invited Henryk Woźniakowski to visit CMU
Carnegie Mellon University
Carnegie Mellon University is a private research university in Pittsburgh, Pennsylvania, United States....
. They pioneered the field of information-based complexity
Information-based complexity
Information-based complexity studies optimal algorithms and computational complexity for the continuous problems which arise in physical science, economics, engineering, and mathematical finance...
, co-authoring three monographs and numerous papers. Woźniakowski is now a tenured professor at both Columbia
Columbia University
Columbia University in the City of New York is a private, Ivy League university in Manhattan, New York City. Columbia is the oldest institution of higher learning in the state of New York, the fifth oldest in the United States, and one of the country's nine Colonial Colleges founded before the...
and the University of Warsaw
University of Warsaw
The University of Warsaw is the largest university in Poland and one of the most prestigious, ranked as best Polish university in 2010 and 2011...
, Poland.
In 1978, while on sabbatical at Berkeley, he was recruited by Peter Likins
Peter Likins
Peter William Likins was president of the University of Arizona from 1997 until his retirement in summer 2006.Previous posts in order of most recent were:*President of Lehigh University...
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.
In 1980 he co-authored A General Theory of Optimal Algorithms, Academic Press, with Woźniakowski. This was the first research monograph on information-based complexity. 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 Journal of Complexity. This was probably the first journal which had complexity in the sense of computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*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
United States National Academies
The United States National Academies comprises four organizations:* National Academy of Sciences * National Academy of Engineering * Institute of Medicine * National Research Council...
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
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
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 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
Alfred P. Sloan Foundation
The Alfred P. Sloan Foundation is a philanthropic non-profit organization in the United States. It was established in 1934 by Alfred P. Sloan, Jr., then-President and Chief Executive Officer of General Motors.-Overview:...
. The goal was to enrich science in the same way that the work of Gödel
Kurt Gödel
Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...
and Turing
Alan Turing
Alan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...
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 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
Scuola Normale Superiore di Pisa
The Scuola Normale Superiore di Pisa, also known in Italian as Scuola Normale , is a public higher learning institution in Italy. It was founded in 1810, by Napoleonic decree, as a branch of the École Normale Supérieure of Paris...
in Pisa. He invited Arthur Werschulz to join him in publishing the lectures. The lectures appeared in expanded form in Complexity and Information, Cambridge University Press
Cambridge University Press
Cambridge University Press is the publishing business of the University of Cambridge. Granted letters patent by Henry VIII in 1534, it is the world's oldest publishing house, and the second largest university press in the world...
, 1998.
In 1994 he asked a PhD student, Spassimir Paskov, to compare the Monte Carlo method
Monte Carlo method
Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...
(MC) with the Quasi-Monte Carlo method
Quasi-Monte Carlo method
In numerical analysis, a quasi-Monte Carlo method is a method for the computation of an integral that is based on low-discrepancy sequences...
(QMC) when calculating a collateralized mortgage obligation
Collateralized mortgage obligation
A collateralized mortgage obligation is a type of financial debt vehicle that was first created in 1983 by the investment banks Salomon Brothers and First Boston for U.S. mortgage lender Freddie Mac. A collateralized mortgage obligation (CMO) is a type of financial debt vehicle that was first...
(CMO) Traub had obtained from Goldman Sachs
Goldman Sachs
The Goldman Sachs Group, Inc. is an American multinational bulge bracket investment banking and securities firm that engages in global investment banking, securities, investment management, and other financial services primarily with institutional clients...
. This involved the numerical approximation of a number of integrals in
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 theoryNumber theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
believed QMC should not be used for integrals of dimension greater than
. Paskov and Traub reported their results to a number of Wall StreetWall Street
Wall Street refers to the financial district of New York City, named after and centered on the eight-block-long street running from Broadway to South Street on the East River in Lower Manhattan. Over time, the term has become a metonym for the financial markets of the United States as a whole, or...
firms to considerable initial skepticism. They first published the results in Paskov and Traub Faster Evaluation of Financial Derivatives, Journal of Portfolio Management 22, 1995, 113-120. 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. 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
New York Academy of Sciences
The New York Academy of Sciences is the third oldest scientific society in the United States. An independent, non-profit organization with more than members in 140 countries, the Academy’s mission is to advance understanding of science and technology...
. The medal was awarded by Mayor Rudy Giuliani
Rudy Giuliani
Rudolph William Louis "Rudy" Giuliani KBE is an American lawyer, businessman, and politician from New York. He served as Mayor of New York City from 1994 to 2001....
in a ceremony in Gracie Mansion
Gracie Mansion
thumb|250px|Western sideGracie Mansion is the official residence of the mayor of the City of New York. Built in 1799, it is located in Carl Schurz Park, at East End Avenue and Eighty-eighth Street in Manhattan...
, the home of New York City's mayor.
Moore's law
Moore's Law
Moore's law describes a long-term trend in the history of computing hardware: the number of transistors that can be placed inexpensively on an integrated circuit doubles approximately every two years....
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
Quantum mechanics
Quantum mechanics, also known as quantum physics or quantum theory, is a branch of physics providing a mathematical description of much of the dual particle-like and wave-like behavior and interactions of energy and matter. It departs from classical mechanics primarily at the atomic and subatomic...
. Traub and his colleagues decided to work on continuous quantum computing. The motivation is that most problems in physical science, engineering, and mathematical finance
Mathematical finance
Mathematical finance is a field of applied mathematics, concerned with financial markets. The subject has a close relationship with the discipline of financial economics, which is concerned with much of the underlying theory. Generally, mathematical finance will derive and extend the mathematical...
have continuous mathematical models.
In 2005 Traub donated some 100 boxes of archival material to the Carnegie Mellon University Library. This collection is being digitized.
Personal
He has two daughters, Claudia Traub-Cooper and Hillary Spector. He lives in Manhattan and Santa Fe with his wife, noted author Pamela McCorduckPamela McCorduck
Pamela McCorduck is the author of a number of books concerning the history and philosophical significance of artificial intelligence, the future of engineering and the role of women and technology. She is also the author of three novels. She is a contributor to Omni, New York Times, Daedalus, the...
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 EngineeringNational Academy of EngineeringThe National Academy of Engineering is a government-created non-profit institution in the United States, that was founded in 1964 under the same congressional act that led to the founding of the National Academy of Sciences...
, 1985 - Founding Chair, Computer Science and Telecommunications Board, National Academies, 1986–92, 2005-
- Sherman FairchildSherman FairchildSherman Mills Fairchild was an inventor and serial entrepreneur who founded over 70 companies namely Fairchild Aircraft, Fairchild Industries, Fairchild Aviation Corporation and Fairchild Camera and Instrument. Fairchild made significant contributions to the aviation industry and was inducted into...
Distinguished Scholar, California Institute of TechnologyCalifornia Institute of TechnologyThe California Institute of Technology is a private research university located in Pasadena, California, United States. Caltech has six academic divisions with strong emphases on science and engineering...
, 1991-2 - Distinguished Senior Scientist Award, 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. PioreEmanuel R. PioreEmanuel Ruben Piore was a scientist and a manager of industrial research.Piore was born on 19 July 1908 in Vilnius, Lithuania. In 1917, his family moved to the United States, and in 1924, Emanuel Piore became a naturalized citizen of the United States.Piore obtained an undergraduate and a Ph.D...
Medal, IEEE - 1992 Distinguished Service Award, Computing Research AssociationComputing Research AssociationThe Computing Research Association is an association of more than 220 North American academic departments of computer science, computer engineering, and related fields; laboratories and centers in industry, government, and academia engaging in basic computing research; and affiliated professional...
- Board of Governors, New York Academy of SciencesNew York Academy of SciencesThe New York Academy of Sciences is the third oldest scientific society in the United States. An independent, non-profit organization with more than members in 140 countries, the Academy’s mission is to advance understanding of science and technology...
, 1986-9 (Executive Committee 1987-89) - Fellow: American Association for the Advancement of ScienceAmerican Association for the Advancement of ScienceThe American Association for the Advancement of Science is an international non-profit organization with the stated goals of promoting cooperation among scientists, defending scientific freedom, encouraging scientific responsibility, and supporting scientific education and science outreach for the...
, 1971; ACMAssociation for Computing MachineryThe Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
1994; New York Academy of SciencesNew York Academy of SciencesThe New York Academy of Sciences is the third oldest scientific society in the United States. An independent, non-profit organization with more than members in 140 countries, the Academy’s mission is to advance understanding of science and technology...
, 1999 - 1999 New York City Mayor's Award for Excellence in Science and Technology
- Search Committee, President, National Academy of EngineeringNational Academy of EngineeringThe National Academy of Engineering is a government-created non-profit institution in the United States, that was founded in 1964 under the same congressional act that led to the founding of the National Academy of Sciences...
1994-5 - Festschrift for Joseph F. Traub, Academic Press, 1993
- Festschrift for Joseph F. Traub, Elsevier, 2004
- Honorary Doctorate of Science, University of Central FloridaUniversity of Central FloridaThe University of Central Florida, commonly referred to as UCF, is a metropolitan public research university located in Orlando, Florida, United States...
, 2001 - Founding Editor-in-Chief, Journal of Complexity, 1985-
Selected monographs
- Iterative Methods for the Solution of Equations, Prentice Hall, 1964. Reissued Chelsea Publishing Company, 1982; Russian translation MIR, 1985; Reissued Amarican 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
- 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).
External links
- Joseph Traub's Columbia homepage
- Joseph Traub digital archive at Carnegie Mellon
- Computer Science and Telecommunications Board, National Academies
- Research monograph Complexity and Information
- Charles Babbage Institute Oral History of Joseph Traub
- SIAM Oral History
- Homepage of Journal of Complexity
- Henryk Woźniakowski Columbia homepage
- Anargyros Papageorgiou Columbia homepage
- Pamela McCorduck homepage
- Publications referring to the Jenkins-Traub method
- Homepage of Schloss Dagstuhl
- CMU Distinguished Lecture Video
- CMU 50th Anniversary Video
- List of computer scientists