Publications: Complete List




Books

		Essays on the Complexity of Continuous Problems, European Mathematical Society, Zurich, 2009 (with E. Novak, I. H. Sloan, and H. Wozniakowski). Complexity and Information, Cambridge University Press, 1998 (with A. G. Werschulz). Proceedings, Fundamental Sources of Unpredictability (edited by J. Hartle, P. Hut, and J. F. Traub) Special issue Complexity, Fall, 1997 . Information-Based Complexity, Academic Press, 1988 (with G. Wasilkowski and H. Wozniakowski). Cohabiting with Computers (editor) William Kaufmann, Inc., 1985. Information, Uncertainty, Complexity, Addison-Wesley, 1983 (with G. Wasilkowski and H. Wozniakowski). Russian translation, MIR, 1988. A General Theory of Optimal Algorithms, Academic Press, 1980 (with H. Wozniakowski). Russian translation, MIR, 1983. Algorithms and Complexity: New Directions and Recent Results (editor) Academic Press, 1976. Analytic Computational Complexity (editor) Academic Press, 1975. Complexity of Sequential and Parallel Numerical Algorithms (editor) Academic Press, 1973. Iterative Methods for the Solution of Equations, Prentice Hall, 1964. Reissued Chelsea Publishing Company, 1982. Russian translation, MIR, 1985.

Papers

	Variational Calculations of the 2³S State of Helium. Phys. Rev. 111, 1958, 1098-1108. Variational Calculations of the 2³P State of Helium. Phys. Rev. 116, 1959, 914-919. On a Class of Iteration Formulas and Some Historical Notes. Communications of the ACM 4, 1961, 276-278. Functional Iteration and the Calculation of Roots. Proceedings of the 1961 National ACM Conference, 5A-1 to 5A-4. A Macro Compiler that Counts Machine Cycles. Bell Labs Report, 1961 (with P.M. Sherman). The Theory of Multipoint Iteration Functions. Proceedings of the 1962 ACM National Conference, 80-81. Interpolatively Generated Iteration Functions. Proceedings of the 1963 ACM National Conference. On Lagrange-Hermite Interpolation. SIAM Review 12, 1964, 886-891. Globally Convergent Iteration Functions. Proceedings IFIP Congress 2, 1965, 483-484. Generalized Sequences with Applications to the Discrete Calculus. Math. Comp. 19, 1965, 177-200. A Proposed System for the Computer-Aided Distribution of Laboratories Technical Memoranda. Bell Labs Report (with W. S. Brown and J.B. Kruskal). Construction of Globally Convergent Iteration Functions for the Solution of Polynomial Equations. Bulletin AMS 71, 1965, 894-895. Associated Polynomials and the Solution of Linear Problems. SIAM Review 8, 1966, 277-301. A Class of Globally Convergent Iteration Functions for the Solution of Polynomial Equations. Math. Comp. 20, 1966, 113-138. The Future of Scientific Journals. Science, 158, 1966, 1153-1159 (with W. S. Brown and J.R. Pierce). The Calculation of Zeros of Polynomials and Analytic Functions. Proceedings of a Symposium on Mathematical Aspects of Computer Science, American Mathematical Society, 1967, 138-152. The Solution of Transcendental Equations. In Mathematical Methods for Digital Computers, edited by Ralston and Wilf, Vol. 2, 1968, 171-184. The Bell Laboratories Numerical Mathematics Program Library Project. Proceedings of the 1968 ACM National Conference, 485-489 (with W.M. Gentleman). MERCURY - A System for the Computer Aided Distribution of Technical papers. Journal of the ACM 16, 1969, 13-25 (with W. S. Brown). An Algorithm for an Automatic General Polynomial Solver. Constructive Aspects of the Fundamental Theorem of Algebra, edited by Dejon and Henrici, Wiley-Interscience, 1969, 151-180 (with M.A. Jenkins). Solving Equations on a Computer. Bell Labs Report, 1969. 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). A Three-Stage Algorithm for Real Polynomials Using Quadratic Iteration. SIAM Journal of Numerical Analysis 7, 1970, 545-566 (with M.A. Jenkins). The Shifted QR Algorithm for Hermitian Matrices. Linear Algebra and Its Applications 4, 1971, 137-154 (with T.J. Dekker). An Analysis of the Shifted LR Algorithm. Numerische Mathematik 17, 1971, 179-188 (with T.J. Dekker). Optimal Iterative Processes: Theorems and Conjectures. Proceedings IFIP Congress Booklet TA-1, 1971, 29-32. High Quality Portable Numerical Mathematics Software. Mathematical Software, Academic Press, New York, 1971, 131-139 (with M.A. Jenkins). On Euclid's Algorithm and the Theory of Subresultants. Journal of the ACM 18, 1971, 505-514 (with W. S. Brown). On the Matrix Polynomial, Lambda-Matrix and Block Eigenvalue Problems. CMU Report, 1971, 97-99 (with J.E. Dennis, Jr. and R. P. Weber). Zeros of a Complex Polynomial (C2), Algorithm 419. Communications of the ACM 15, 1972, 97-99 (with M.A. Jenkins). Computational Complexity of Iterative Processes. SIAM Journal on Computing 1, 1972, 167-179. The Future of Numerical Mathematics. SIGNUM Newsletter 7, 1972, 21-45. Numerical Mathematics and Computer Science. 25th Anniversary Issue of Communications ACM 15, 1972, 537-541. Iterative Solution of Tridiagonal Systems on Parallel or Vector Computers. In J.F. Traub (editor) Complexity of Sequential and Parallel Numerical Algorithms, Academic Press, 1973, 49-82. Computational Complexity of One-Point and Multipoint Iteration. Complexity of Computation, edited by R. Karp. SIAM-AMS Proceedings 7, American Mathematical Society, 1974, 149-160, (with H.T. Kung). Theory of Optimal Algorithms. Software for Numerical Mathematics edited by D.J. Evans, Academic Press, 1974, 1-13. An Introduction to Some Current Research in Numerical Computational Complexity. Proceedings of the Conference on the Influence of Computing on Mathematical Research and Education, American Mathematical Society, 1974, 47-55. On the Number of Multiplications for the Evaluation of a Polynomial and Some if Its Derivatives. Journal of the ACM, 21, 1974, 161-167 (with M. Shaw). Parallel Algorithms and Parallel Computational Complexity. Proceedings IFIP Congress, 1974, 685-687. Principles for Testing Polynomial Zerofinding Programs. ACM Trans. on Mathematical Software 1, 1975, 26-34 (with M.A. Jenkins). Accelerated Iterative Methods for the Solution of Tridiagonal Systems on Parallel Computers. Journal of the ACM 23, 1976, 636-654 (with D. E. Heller and D. K. Stevenson). Order of Vector Recurrences with Applications to Nonlinear Iteration, Parallel Algorithms, and the Power Method. CMU Report (with A. Feldstein). Analysis of a Family of Algorithms for the Evaluation of a Polynomial and Some of Its Derivatives. CMU Report, 1975 (with M. Shaw). Recent Results and Open Problems in Computational Complexity. Theorie des Algorithmes, des Languages et de la Programmation, Seminaries I.R.I.A., October 1974-June 1975. Strict Lower and Upper Bounds on Iterative Complexity. Analytic Computational Complexity, edited by J.F. Traub, Academic Press, 1975, 15-34 (with H. Wozniakowski). Algorithms for Solvents of Matrix Polynomials. SIAM Journal on Numerical Analysis 15, 1978, 523-533 (with J.E. Dennis and R. P. Weber). Optimal Order and Efficiency for Iterations with Two Evaluations. SIAM Journal on Numerical Analysis 13, 1976, 84-89 (with H.T. Kung). Numerical Analysis and Computational Complexity (extended abstract). Proceedings of the Numerical Analysis Seminar, University of Paris, France. Optimal Linear Information for the Solution of Non-Linear Operator Equations. Algorithms and Complexity: New Directions and Recent Results, edited by J.F. Traub, Academic Press, 1976, 103-119 (with H. Wozniakowski). Some General Observations on Ph.D. Production in Computer Science. SIGCSE Newsletter 8, 1976, 8-9. The Algebraic Theory of Matrix Polynomials. SIAM Journal on Numerical Analysis 13, 1976, 831-845 (with J.E. Dennis and R. P. Weber). Asymptotic Behavior of Vector Recurrences with Applications. Mathematics of Computation 31, 1977, 180-192 (with A. Feldstein). Convergence and Complexity of Newton Iteration for Operator Equations. Journal of the ACM 26, 1979, 250-258. Optimal Radius of Convergence of Interpolatory Iterations for Operator Equations. Equationes Mathematica 21, 1976, 151-172 (with H. Wozniakowski). Convergence and Complexity of Interpolatory-Newton Iteration in a Banach Space. Comput. Math. Appl.6, 1980, 385-400 (with H. Wozniakowski). Selection of Good Algorithms from a Family of Algorithms for Polynomial Derivatives. Information Processing Letters 6, 1977, 141-145 (with Mary Shaw). General Theory of Optimal Error Algorithms and Analytic Complexity: Part A. General Information Model. CMU Report, 1977 (with H. Wozniakowski). Recent Results and Open Problems in Analytic Computational Complexity (extended abstract). Proceedings of the Banach Center's Mathematical Models and Numerical Methods Semester 3, Warsaw, Poland, 1978, 269-272. All Algebraic Functions Can Be Computed Fast. Journal of the ACM 25, 1978, 245-260. Also appeared in Analyse et Controle de Systems, Seminaries IRIA, 1977, 133-152. On the Complexity of Composition and Generalized Composition of Power Series. SIAM Journal on Computation 9, 1980, 54-66 (with R. Brent). General Theory of Optimal Error Algorithms and Analytic Complexity: Part B. Iterative Information Model. CMU Report, 1978 (with H. Wozniakowski). The Influence of Agorithms and Heuristics on Mathematics, Science, and Education. Proceedings of the Tenth Anniversary Symposium, I.R.I.A., Paris, France, 1978. History and Annotated Bibliography for Analytic Complexity. CMU Report, 1979 (with H. Wozniakowski). On A Soviet Algorithm for the Linear Programming Problem. Columbia University Report, 1979 (with H. Wozniakowski). Quo Vadimus: Computer Science in a Decade. Communications of the ACM 24, 1981, 351-369 (J.F. Traub et al.). Computational Complexity. Encyclopedia of Computer Science, Van Nostrand Reinhold, 1983. A Discipline in Crisis. Communications of the ACM 24, 1981 370-374, (J.F. Traub et al.). What will be the Intellectual Impact of Computers? Proceedings, General Education Seminar, Columbia University, 1982-83, vol. 11, 83-92. Complexity of Linear Programming. Operations Research Letters 1, 1982, 59-62 (with H. Wozniakowski). Ways to Meet the Crisis in Computer Science. Communications of the ACM 26, 1983 (J.F. Traub et al.). On the Optimal Solution of Large Linear Systems, Journal of the ACM 31, 1984, 545-559, (with H. Wozniakowski). On the Optimal Solution of Large Linear Systems. Journal of the ACM 31, 1984, 545-559 (with H. Wozniakowski). Average Case Optimality for Linera Problems, Journal TCS 29, 1984, 1-25 (with G. Wasilkowski and H. Wozniakowski). Statistical Security of a Statistical Data Base. ACM Trans. on Database Systems 9, 1984, 672-679 (with H. Wozniakowski and Y. Yemini). Information and Computation. In Advances in Computers 23, M Yovits (editor), Academic Press, 1984 (with H. Wozniakowski). When is Nonadaption Information as Powerful as Adaption Information? Proceedings of the 23rd IEEE Conference on Decision and Control, Las Vegas, Nevada, 1984, 1536-1540 (with G. Wasilkowski and 14. Wozniakowski). Optimal Integration for Functions of Bounded Variation. Mathematics of Computation 45, 1985, 505-512 (with D. Lee). Complexity of Approximately Solved Problems. Journal of Complexity 1, 1985, 3- 10. Information-Based Complexity. Nature 327, July, 1987, 29-33 (with E. Packel). Introduction to Information-Based Complexity. In Complexity in Information Theory, Y.S. Abu-Mostafa (editor), Springer Verlag, 1988. National Agenda and Priorities in Computer Science and Engineering Research. Columbia University Report. Industry-University Symposium on Computer Science and Engineering, sponsored by NSF and IBM, Yorktown Heights, New York; April 24-26, 1989. The National Agenda in Computer Science and Technology. IEEE Computer, March 1990, 83-84. The Federal High Performance Computing Initiative, testimony to the Subcommittee on Science, Research and Technology, US House of Representatives. Columbia University Report, 1989. High Performance Computing in Science and Engineering. Proceedings of Strategic Directions in Computer Science Research ACM/CRB Conference, Washington, DC; October 11-13, 1989. Computation and Science. Computing Research News, 1990. Information-Based Complexity: New Questions for Mathematicians. Mathematical Intelligencer 13, 1991, 34-43 (with H. Wozniakowski). What is Scientifically Knowable? Proceedings, Twenty Fifth Anniversary Symposium, School of Computer Science, Carnegie-Mellon University, Addison-Wesley, 1991, 489-503. Theory and Applications of Information-Based Complexity. Lectures in Complex Systems, Santa Fe Institute Studies in the Sciences of Complexity, Lect. Vol. III (L. Nadel and D. Stein, eds.), Addison-Wesley, Massachusetts, 1991, 163-193 (with H. Wozniakowski). Some Thoughts on the Nature of Continuous Computational Complexity. In Algorithms and Complexity for Continuous Problems, Dagstuhl Seminar Report, April 19, 1991 (E. Novak, J.F. Traub and H. Wozniakowski, eds.), IBFI, Saarbrucken, Germany, 1991, 15-16. Information-Based Complexity: Recent Results and 0pen Problems. In Proceedings of Fundamentals of Computation Theory, FCT 91, Gosen, Germany, September 9-13, 1991, Springer-Verlag, 1991. The Santa Fe Institute: An Overview. NetView, Global Business Network, Emeryville, California, December, 1991 (with P. McCorduck). Perspectives on Information-Based Complexity. Bull. Amer. Math. Soc. 26, 1992, 29-52 (with H. Wozniakowski). Measures of Uncertainty and Information in Computation. Journal of Information Sciences 65, 1992, 253-273 (with E. Packel and H. Wozniakowski). Smale's Work in the Theory of Computation: From Polynomial Zeros to Continuous Complexity. Festschrift in Honor of Steven Smale's 60th birthday, Springer-Verlag, 1993, 317-320. Computational Complexity. Encyclopedia of Computer Science and Engineering, Van Nostrand and Reinhold, New York, 1992, 212-214. Information-Based Complexity. Encyclopedia of Computer Science and Engineering, Van Nostrand and Reinhold, New York, 1992,655-657. The Monte Carlo Algorithm with a Pseudo-Random Number Generator. Mathematics of Computation 58, 1992, 303-339 (with H. Wozniakowski). Recent Progress in Information-Based Complexity. Bulletin European Association Theoretical Computer Science, October, 1993, 142-154 (with H. Wozniakowski). Breaking Intractability. Scientific American, January, 1994, 102-107 (with H. Wozniakowski). Linear Ill-Posed Problems are Solvable on the Average for All Gaussian Measures. Math Intelligencer 16, 1994, 42-48 (with A. G. Werschulz). Demand and Supply of Computer Science and Engineering PhD's. Computer Science News, May, 1994 (with A. Chandra, D. A. Patterson, and P. Young). On Limits, Working Paper, Santa Fe Institute, October, 1994 (with J. Casti) Faster Valuation of Financial Derivatives. Journal of Portfolio Management 22, 1995, 113-120 (with S. Paskov). Breaking Intractability. Scientific American (with, H. Wozniakowski). Translated into German, Italian, Japanese, and Polish. On Reality and Models, in Boundaries and Barriers: On the Limits to Scientific Knowledge, (J. Casti and A. Karlqvist, eds.), Addison-Wesley, 1996, 238-251. Beating Monte Carlo. RISK 9, 1996, 63-65 (with A. Papageorgiou). From Infoware to Infowar, Defining a Decade: Envisioning CSTB'S Second 10 Years, National Academy of Sciences, 1997, 1-7. The Unknown and the Unknowable, Columbia University Computer Science Department, Technical Report, 1997, and on the World Wide Web: http://www.edge.org. Do Negative Results from Formal Systems Limit Scientific Knowledge?, Complexity 3, 1997, 29-31. Faster Evaluation of Multi-Dimensional Integrals, Computers in Physics 11:6, 1997, 574-578 (with A. Papageorgiou). Non-Computability, and Intractability: Does it Matter to Physics?, Columbia University Department of Computer Science, Technical Report, 1998. Varieties of Limits to Scientific Knowledge, Complexity 5, 1998, 33-38 (with P. Hut and D. Ruelle). The Unknown and the Unknowable, The Sciences, January/February, 1999, 39-44. A Continuous Model of Computation (Invited Paper), Physics Today, May, 1999, 39-43. Information-Based Complexity, Encyclopedia of Computer Science and Engineering, 4^th Edition, 2000, 850-854. Information-Based Complexity and Information-Based Optimization (with A. G. Werschulz) Encyclopedia of Optimization, Volume II, 485-489, 2001. Computing:Yesterday, Today, and Tomorrow, Complexity, 6(6), 15-18, 2001 (presented on the occasion of an honorary Doctorate of Science, University of Central Florida. No Curse of Dimensionality for Contraction Fixed Points in the Worst Case? (with J. Rust and H. Wozniakowski), Econometrica, 70(1), 285-329, January 2002. Quantum Path Integration (with H. Wozniakowski), Quantum Information Processing, 1(5), 365-388, October 2002. Qubit Complexity for Continuous Problems, (with A. Papageorgiou), JFPTA, Part I, Vol. VII, 2009, 295-304. Quantum Algorithms and Complexity for Continuous Problems, (with A. Papageorgiou), in “Encyclopedia of Complexity and Systems Science”, Vol. 8, 7118-7135, Springer New York, 2009. A Brief History of Information-Based Complexity, in “Essays on the Complexity of Continuous Problems”, European Mathematical Society, Zurich, 2009. A fast algoritthm for approximating the ground state energy on a quantum computer, (with A. Papageorgiou, I. Petras, C. Zhang) to appear in Mathematics of Computation, 82, 2293, 2013. Quantum algorithms for continuous problems and their applications, (with A. Papageorgiou) to appear in Adv. Chem. Phys., Quantum Information and Computation for Chemistry, S. Kais, A. R. Dinner and S. A. Rice Eds., 154, 2013. Quantum algorithm and circuit design solvin the Poisson equation, (with Y. Cao, A. Papageorgiou, I. Petras, S. Kais) New Journal of Physics, 15, 013021, 2013. Measures of quantum computing speedup, (with A. Papageorgiou) Phys. Rev A, 88, 022316, 2013.