Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

Recent developments in information-based complexity


Authors: Edward W. Packel and Henryk Woźniakowski
Journal: Bull. Amer. Math. Soc. 17 (1987), 9-36
MSC (1985): Primary 65-02, 68Q25
DOI: https://doi.org/10.1090/S0273-0979-1987-15511-X
MathSciNet review: 888879
Full-text PDF

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • I. Adler, R. M. Karp, and R. Shamir (1983), A simplex variant solving an m × d linear program in O(min( m 2, d 2)) expected number of pivot steps, Report UCB CSD 83/158, University of California, Berkeley.
  • I. Adler and N. Megiddo (1985), A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension, J. Assoc. Comput. Mach. 32, 871-895. MR 810342
  • M. Atteia (1965), Fonctions-spline généralisées, C. R. Acad. Sci. Paris 216, 2149-2152. MR 212470
  • N. S. Bakhvalov (1971), On the optimality of linear methods for operator approximation in convex classes of functions, Zh. Vychisl. Mat. Fiz. 11, 244-249.
  • L. Blum and M. Shub (1986), Evaluation of rational functions: Infinite precision is finite cose and tractable on average, SIAM J. Comput. 15, 384-398. MR 837590
  • A. Borodin (1972), Complexity classes of recursive functions and the existence of complexity gaps, J. Assoc. Comput. Mach. 19, 158-174, 576. MR 321355
  • S. Gal and C. A. Micchelli (1980), Optimal sequential and non-sequential procedures for evaluating a functional, Applicable Anal. 10, 105-120. MR 575536
  • R. Holmes (1972), R-splines in Banach spaces, I. Interpolation of linear manifolds, J. Math. Anal. Appl. 40, 547-593. MR 313689
  • J. B. Kadane and G. W. Wasilkowski (1985), Average case ε-complexity: A Bayesian view, Bayesian Statistics 2, Proc. Second Valencia Internat. Meeting (September 6/10, 1983) (J. M. Bernardo, M. H. Degroot, D. V. Lindley, A. F. M. Smith, eds)., 361-374.
  • R. M. Karp (1976), The probabilistic analysis of some combinatorial search algorithms, Algorithms and Complexity: New Directions and Recent Results (J. F. Traub, ed.) Academic Press, New York, 1-19. MR 445898
  • R. M. Karp (1979), Recent advances in probabilistic analysis of graph-theoretic algorithms, Proc. 6th Colloq. Auto. Lang, and Program., Lecture Notes in Computer Sci. 71, 338-339.
  • R. M. Karp (1980), An algorithm to solve the m × n assignment problem in expected time O ( mn log n ), Networks 10, 143-152. MR 569006
  • R. M. Karp and M. Luby (1983), Monte-Carlo algorithms for enumeration and reliability problems, Proc. 24th IEEE Found. of Comp. Sci. Sympos., 56-60.
  • R. M. Karp and M. Luby (1985), A Monte-Carlo algorithm for the multiterminal reliability problem, J. Complexity 1, 45-64. MR 829869
  • J. Kiefer (1953), Sequential minimax search for a maximum, Proc. Amer. Math. Soc. 4, 502-505. MR 55639
  • G. S. Kimeldorf and G. Wahba (1970a), A correspondence between Bayesian estimation on stochastic processes and smoothing by splines, Ann. Math. Statist. 41, 2, 495-502. MR 254999
  • G. S. Kimeldorf and G. Wahba (1970b), Spline functions and stochastic processes, Sankhyā Ser. A 32, 173-180. MR 303594
  • H. H. Kuo (1975), Gaussian measures in Banach spaces, Lecture Notes in Math., vol. 463, Springer-Verlag, Berlin and New York. MR 461643
  • F. M. Larkin (1972), Gaussian measure in Hilbert space and application in numerical analysis, Rocky Mountain J. Math. 2, 378-421. MR 303193
  • D. Lee and G. W. Wasilkowski (1986), Approximation of linear functional on a Banach space with a Gaussian measure, J. Complexity 2, 12-43. MR 925342
  • M. Marcus and H. Minc (1964), A survey of matrix theory and matrix inequalities, Allyn and Bacon, Inc., Boston. MR 162808
  • C. A. Micchelli and T. J. Rivlin (1977), A survey of optimal recovery, Optimal Estimation in Approximation Theory (C. A. Micchelli and T. J. Rivlin, eds.), Plenum Press, New York, 1-54. MR 617931
  • V. P. Motornyj (1973), On the best quadrature formula of the form $\sum \sb{k=1}\spnp\sbkf(x\sbk)$ for some classes of periodic differentiable functions, Dokl. Akad. Nauk SSSR 211, 1060-1062 [English transl.: Soviet Math. Dokl. 14, 1180-1183]. MR 326249
  • A. S. Nemirovsky and D. B. Yudin (1983), Problem complexity and method efficiency in optimization, Wiley-Interscience, New York. Translated from Slozhnost' zadach i effektivnost' metodov optimizatsii. MR 702836
  • S. M. Nikolskij (1950), On the problem of approximation estimate by quadrature formulae (in Russian), Uspekhi Mat. Nauk 5, 165-177.
  • K. Yu. Osipenko (1976), Best approximation of analytic functions from information about their values at a finite number of points (in Russian), Mat. Zametki 19, 29-40 [English transl.: Math. Notes 19, 17-23]. MR 454020
  • E. W. Packel (1986a), Linear problems (with extended range) have linear optimal algorithms, Aequationes Mathematicae 31, 18-25. MR 857683
  • E. W. Packel (1986b), Do linear problems have linear optimal algorithms? SIAM Rev. (to appear). MR 958097
  • A. Papageorgiou and G. W. Wasilkowski (1986), Average case complexity for multivariate problems, Report, Dept. of Computer Science, Columbia University.
  • K. R. Parthasarathy (1967), Probability measures on metric spaces, Academic Press, New York. MR 226684
  • M. O. Rabin (1976), Probabilistic algorithms, Algorithms and Complexity: New Directions and Recent Results (J. F. Traub, ed.), Academic Press, New York, 21-39. MR 464678
  • M. O. Rabin (1983), Randomized Byzantine generals, Proc. 24th IEEE Sympos. Found. of Comp. Sci.
  • M. O. Rabin (1986), Removing singularities through randomization, in progress.
  • J. Renegar (1984), On the efficiency of Newton's method in approximating all zeros of a system of complex polynomials, Report, Colorado State University.
  • J. Sacks and D. Ylvisaker (1970), Statistical designs and integral approximation, Proc. 12th Biennial Seminar Canadian Math. Congr., 115-136. MR 277069
  • A. Sard (1949), Best approximate integration formulas; best approximation formulas, Amer. J. Math. 71, 80-91. MR 29283
  • M. Shub and S. Smale (1985), Computational complexity: On the geometry of polynomials and a theory of cost, Part I, Ann. Sci. École Norm. Sup. 4 serie, 18. MR 803197
  • M. Shub and S. Smale (1986a), Computational complexity: On the geometry of polynomials and a theory of cost, Part II, SIAM J. Comput. 15, 145-161. MR 822199
  • M. Shub and S. Smale (1986b), On the existence of generally convergent algorithms, J. Complexity 2, 2-11. MR 925341
  • K. Sikorski (1982), Bisection is optimal, Numer. Math. 40, 111-117. MR 681817
  • K. Sikorski (1985), Optimal solution of nonlinear equations, J. Complexity 1, 197-209. MR 925428
  • A. V. Skorohod (1974), Integration in Hilbert space, Springer-Verlag, New York. MR 466482
  • S. Smale (1981), The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. 4, 1-36. MR 590817
  • S. Smale (1983a), The problem of the average speed of the simplex method, Mathematical Programming: The State of the Art (A. Bachem et al., eds.), Springer-Verlag, New York, 530-539. MR 717413
  • S. Smale (1983b), On the average number of steps in the simplex method of linear programming, Math. Programming 27, 241-262. MR 725621
  • S. Smale (1985), On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. 13, 87-121. MR 799791
  • S. A. Smolyak (1965), On optimal restoration of functions and functional of them, Candidate's Dissertation, Moscow State Univ. (Russian).
  • A. V. Suldin, Wiener measure and its application to approximation methods, I, II, Izv. Vyssh. Uchebn. Zaved. Mat. 1959, no. 6 (13), 145-158, 1960, no. 5 (18), 165-179 (Math. Rev. 28 #722, 29 #1482). MR 157489
  • J. F. Traub (1961), On functional iteration and the calculation of roots, Preprints of Papers 16th Nat. ACM Conf., Session 5A-1, pp. 1-4, Los Angeles. MR 144459
  • J. F. Traub (1964), Iterative methods for the solution of equations, Prentice-Hall, Englewood Cliffs, New Jersey; reprinted by Chelsea Press, New York, 1982. MR 169356
  • J. F. Traub, G. W. Wasilkowski and H. Woźniakowski (1983), Information, uncertainty, complexity, Addison Wesley, Reading, Mass. MR 680041
  • J. F. Traub, G. W. Wasilkowski and H. Woźniakowski (1984), Average case optimality for linear problems, Journal TCS 29, 1-25. MR 742399
  • J. F. Traub and H. Woźniakowski (1980), A general theory of optimal algorithms, Academic Press, New York. MR 584446
  • G. M. Trojan (1984), Asymptotic setting for linear problems, unpublished manuscript.
  • S. Twomey (1977), Introduction to mathematics of inversion in remote sensing and indirect measurements, Developments in Geomathematics 3, Elsevier Scientific Publ., Amsterdam.
  • N. N. Vakhania (1981), Probability distributions on linear spaces, North-Holland, New York. MR 626346
  • G. Wahba (1971), On the regression design problem of Sacks and Ylvisaker, Ann. Math. Statist. 42, 1035-1053. MR 279955
  • G. Wahba (1978), Improper priors, spline smoothing and the problem of guarding against model errors in regression, J. Royal Statist. Soc. B 40, 3, 364-372. MR 522220
  • G. W. Wasilkowski (1983), Local average error, Report, Dept. of Computer Science, Columbia University.
  • G. W. Wasilkowski (1985), Average case optimality, J. Complexity 1, 107-117. MR 829871
  • G. W. Wasilkowski (1986a), Information of varying cardinality, J. Complexity 2, 204-228. MR 922813
  • G. W. Wasilkowski (1986b), Optimal algorithms for linear problems with Gaussian measures, Rocky Mountain J. Math. 16, 727-749. MR 871033
  • G. H. Wasilkowski and H. Woźniakowski (1982), Average case optimal algorithms in Hilbert spaces, Report, Dept. of Computer Science, Columbia University; also in J. Approx. Theory 47, 17-25. MR 843452
  • G. H. Wasilkowski and H. Woźniakowski (1984a), Can adaption help on the average?, Numer. Math. 44, 169-190. MR 753951
  • G. H. Wasilkowski and H. Woźniakowski (1984b), On optimal algorithms in an asymptotic model with Gaussian measure, Report, Dept of Computer Science, Columbia University.
  • A. G. Werschulz (1982a), Optimal error properties of finite element methods for second order Dirichlet problems, Math. Comp. 38, 401-413. MR 645658
  • A. G. Werschulz (1982b), Finite element methods are not always optimal, Report, Univ. of Maryland, Baltimore County.
  • A. G. Werschulz (1985a), Complexity of differential and integral equations, J. Complexity 1, 232-255. MR 925430
  • A. G. Werschulz (1985b), What is the complexity of elliptic systems?, J. Approx. Theory 45, 69-89. MR 808121
  • A. G. Werschulz and H. Woźniakowski (1986), Are linear algorithms always good for linear problems?, Aequationes Math. 31, 202-211. MR 867518
  • H. Woźniakowski (1986a), Information-based complexity, Ann. Rev. Comput. Sci. Volume 1, 319-380. MR 876097
  • H. Woźniakowski (1986b), Probabilistic setting of information-based complexity, J. Complexity 2, 255-269. MR 922816
  • H. Woźniakowski (1986c), Complexity of integration in different settings, Proc. Optimal Algorithms (Sofia, Bulgaria), 235-240.
  • D. Ylvisaker (1975), Designs on random fields, A Survey of Statistical Design and Linear Models (J. N. Srivastava, ed.), North-Holland, New York, 593-607. MR 428662

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (1985): 65-02, 68Q25

Retrieve articles in all journals with MSC (1985): 65-02, 68Q25


Additional Information

DOI: https://doi.org/10.1090/S0273-0979-1987-15511-X

American Mathematical Society