Recent developments in information-based complexity
HTML articles powered by AMS MathViewer
- by Edward W. Packel and Henryk Woźniakowski PDF
- Bull. Amer. Math. Soc. 17 (1987), 9-36
References
-
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.
- Ilan Adler and Nimrod Megiddo, A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension, J. Assoc. Comput. Mach. 32 (1985), no. 4, 871–895. MR 810342, DOI 10.1145/4221.4222
- Marc Atteia, “Spline-fonctions” généralisées, C. R. Acad. Sci. Paris 261 (1965), 2149–2152 (French). 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.
- Lenore Blum and Michael Shub, Evaluating rational functions: infinite precision is finite cost and tractable on average, SIAM J. Comput. 15 (1986), no. 2, 384–398. MR 837590, DOI 10.1137/0215026
- A. Borodin, Computational complexity and the existence of complexity gaps, J. Assoc. Comput. Mach. 19 (1972), 158–174; corrigendum, ibid. 19 (1972), 576. MR 321355, DOI 10.1145/321679.321691
- Shmuel Gal and Charles A. Micchelli, Optimal sequential and nonsequential procedures for evaluating a functional, Applicable Anal. 10 (1980), no. 2, 105–120. MR 575536, DOI 10.1080/00036818008839292
- Richard Holmes, $R$-splines in Banach spaces. I. Interpolation of linear manifolds, J. Math. Anal. Appl. 40 (1972), 574–593. MR 313689, DOI 10.1016/0022-247X(72)90003-0 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.
- Richard M. Karp, The probabilistic analysis of some combinatorial search algorithms, Algorithms and complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976) Academic Press, New York, 1976, pp. 1–19. MR 0445898 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.
- Richard M. Karp, An algorithm to solve the $m\times n$ assignment problem in expected time $O(mn\,\textrm {log}\,n)$, Networks 10 (1980), no. 2, 143–152. MR 569006, DOI 10.1002/net.3230100205 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.
- Richard M. Karp and Michael Luby, Monte Carlo algorithms for the planar multiterminal network reliability problem, J. Complexity 1 (1985), no. 1, 45–64. MR 829869, DOI 10.1016/0885-064X(85)90021-4
- J. Kiefer, Sequential minimax search for a maximum, Proc. Amer. Math. Soc. 4 (1953), 502–506. MR 55639, DOI 10.1090/S0002-9939-1953-0055639-3
- George S. Kimeldorf and Grace Wahba, A correspondence between Bayesian estimation on stochastic processes and smoothing by splines, Ann. Math. Statist. 41 (1970), 495–502. MR 254999, DOI 10.1214/aoms/1177697089
- George S. Kimeldorf and Grace Wahba, Spline functions and stochastic processes, Sankhyā Ser. A 32 (1970), 173–180. MR 303594
- Hui Hsiung Kuo, Gaussian measures in Banach spaces, Lecture Notes in Mathematics, Vol. 463, Springer-Verlag, Berlin-New York, 1975. MR 0461643
- F. M. Larkin, Gaussian measure in Hilbert space and applications in numerical analysis, Rocky Mountain J. Math. 2 (1972), no. 3, 379–421. MR 303193, DOI 10.1216/RMJ-1972-2-3-379
- D. Lee and G. W. Wasilkowski, Approximation of linear functionals on a Banach space with a Gaussian measure, J. Complexity 2 (1986), no. 1, 12–43. MR 925342, DOI 10.1016/0885-064X(86)90021-X
- Marvin Marcus and Henryk Minc, A survey of matrix theory and matrix inequalities, Allyn and Bacon, Inc., Boston, Mass., 1964. MR 0162808
- C. A. Micchelli and T. J. Rivlin, A survey of optimal recovery, Optimal estimation in approximation theory (Proc. Internat. Sympos., Freudenstadt, 1976) Plenum, New York, 1977, pp. 1–54. MR 0617931
- V. P. Motornyĭ, The best quadrature formula of the form $\sum _{k=1}^{n}p_{k}f(x_{k})$ for certain classes of periodic differentiable functions, Dokl. Akad. Nauk SSSR 211 (1973), 1060–1062 (Russian). MR 0326249
- A. S. Nemirovsky and D. B. Yudin, Problem complexity and method efficiency in optimization, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Inc., New York, 1983. Translated from the Russian and with a preface by E. R. Dawson. MR 702836 S. M. Nikolskij (1950), On the problem of approximation estimate by quadrature formulae (in Russian), Uspekhi Mat. Nauk 5, 165-177.
- K. Ju. Osipenko, Best approximation of analytic functions from information about their values at a finite number of points, Mat. Zametki 19 (1976), no. 1, 29–40 (Russian). MR 454020
- Edward W. Packel, Linear problems (with extended range) have linear optimal algorithms, Aequationes Math. 31 (1986), no. 1, 18–25. MR 857683, DOI 10.1007/BF02188168
- Edward W. Packel, Do linear problems have linear optimal algorithms?, SIAM Rev. 30 (1988), no. 3, 388–403. MR 958097, DOI 10.1137/1030091 A. Papageorgiou and G. W. Wasilkowski (1986), Average case complexity for multivariate problems, Report, Dept. of Computer Science, Columbia University.
- K. R. Parthasarathy, Probability measures on metric spaces, Probability and Mathematical Statistics, No. 3, Academic Press, Inc., New York-London, 1967. MR 0226684
- Michael O. Rabin, Probabilistic algorithms, Algorithms and complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976) Academic Press, New York, 1976, pp. 21–39. MR 0464678 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.
- Jerome Sacks and Donald Ylvisaker, Statistical designs and integral approximation, Proc. Twelfth Biennial Sem. Canad. Math. Congr. on Time Series and Stochastic Processes; Convexity and Combinatorics (Vancouver, B.C., 1969) Canad. Math. Congr., Montreal, Que., 1970, pp. 115–136. MR 0277069
- Arthur Sard, Best approximate integration formulas; best approximation formulas, Amer. J. Math. 71 (1949), 80–91. MR 29283, DOI 10.2307/2372095
- Mike Shub and Steven Smale, Computational complexity. On the geometry of polynomials and a theory of cost. I, Ann. Sci. École Norm. Sup. (4) 18 (1985), no. 1, 107–142. MR 803197, DOI 10.24033/asens.1486
- M. Shub and S. Smale, Computational complexity: on the geometry of polynomials and a theory of cost. II, SIAM J. Comput. 15 (1986), no. 1, 145–161. MR 822199, DOI 10.1137/0215011
- Michael Shub and Steve Smale, On the existence of generally convergent algorithms, J. Complexity 2 (1986), no. 1, 2–11. MR 925341, DOI 10.1016/0885-064X(86)90020-8
- K. Sikorski, Bisection is optimal, Numer. Math. 40 (1982), no. 1, 111–117. MR 681817, DOI 10.1007/BF01459080
- K. Sikorski, Optimal solution of nonlinear equations, J. Complexity 1 (1985), no. 2, 197–209. Complexity of approximately solved problems (Morningside Heights, N.Y., 1985). MR 925428, DOI 10.1016/0885-064X(85)90011-1
- A. V. Skorohod, Integration in Hilbert space, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 79, Springer-Verlag, New York-Heidelberg, 1974. Translated from the Russian by Kenneth Wickwire. MR 0466482, DOI 10.1007/978-3-642-65632-3
- Steve Smale, The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 1–36. MR 590817, DOI 10.1090/S0273-0979-1981-14858-8
- S. Smale, The problem of the average speed of the simplex method, Mathematical programming: the state of the art (Bonn, 1982) Springer, Berlin, 1983, pp. 530–539. MR 717413
- Steve Smale, On the average number of steps of the simplex method of linear programming, Math. Programming 27 (1983), no. 3, 241–262. MR 725621, DOI 10.1007/BF02591902
- Steve Smale, On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. (N.S.) 13 (1985), no. 2, 87–121. MR 799791, DOI 10.1090/S0273-0979-1985-15391-1 S. A. Smolyak (1965), On optimal restoration of functions and functional of them, Candidate’s Dissertation, Moscow State Univ. (Russian).
- A. V. Sul′din, Wiener measure and its applications to approximation methods. I, Izv. Vysš. Učebn. Zaved. Matematika 1959 (1959), no. 6 (13), 145–158 (Russian). MR 0157489
- J. F. Traub, Comparison of iterative methods for the calculation of $n$th roots. , Comm. ACM 4 (1961), 143–145. MR 0144459, DOI 10.1145/366199.366252
- J. F. Traub, Iterative methods for the solution of equations, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964. MR 0169356
- Joseph Frederick Traub, G. W. Wasilkowski, and H. Woźniakowski, Information, uncertainty, complexity, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. MR 680041
- J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Average case optimality for linear problems, Theoret. Comput. Sci. 29 (1984), no. 1-2, 1–25. MR 742399, DOI 10.1016/0304-3975(84)90009-4
- Joe Fred Traub and H. Woźniakowsi, A general theory of optimal algorithms, ACM Monograph Series, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. 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, Probability distributions on linear spaces, North-Holland Series in Probability and Applied Mathematics, North-Holland Publishing Co., New York-Amsterdam, 1981. Translated from the Russian by I. I. Kotlarski. MR 626346
- Grace Wahba, On the regression design problem of Sacks and Ylvisaker, Ann. Math. Statist. 42 (1971), 1035–1053. MR 279955, DOI 10.1214/aoms/1177693331
- Grace Wahba, Improper priors, spline smoothing and the problem of guarding against model errors in regression, J. Roy. Statist. Soc. Ser. B 40 (1978), no. 3, 364–372. MR 522220, DOI 10.1111/j.2517-6161.1978.tb01050.x G. W. Wasilkowski (1983), Local average error, Report, Dept. of Computer Science, Columbia University.
- G. W. Wasilkowski, Average case optimality, J. Complexity 1 (1985), no. 1, 107–117. MR 829871, DOI 10.1016/0885-064X(85)90023-8
- G. W. Wasilkowski, Information of varying cardinality, J. Complexity 2 (1986), no. 3, 204–228. MR 922813, DOI 10.1016/0885-064X(86)90002-6
- G. W. Wasilkowski, Optimal algorithms for linear problems with Gaussian measures, Rocky Mountain J. Math. 16 (1986), no. 4, 727–749. MR 871033, DOI 10.1216/RMJ-1986-16-4-727
- G. W. Wasilkowski and H. Woźniakowski, Average case optimal algorithms in Hilbert spaces, J. Approx. Theory 47 (1986), no. 1, 17–25. MR 843452, DOI 10.1016/0021-9045(86)90043-2
- G. W. Wasilkowski and H. Woźniakowski, Can adaption help on the average?, Numer. Math. 44 (1984), no. 2, 169–190. MR 753951, DOI 10.1007/BF01410103 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.
- Arthur G. Werschulz, Optimal error properties of finite element methods for second order elliptic Dirichlet problems, Math. Comp. 38 (1982), no. 158, 401–413. MR 645658, DOI 10.1090/S0025-5718-1982-0645658-4 A. G. Werschulz (1982b), Finite element methods are not always optimal, Report, Univ. of Maryland, Baltimore County.
- Arthur G. Werschulz, Complexity of differential and integral equations, J. Complexity 1 (1985), no. 2, 232–255. Complexity of approximately solved problems (Morningside Heights, N.Y., 1985). MR 925430, DOI 10.1016/0885-064X(85)90013-5
- Arthur G. Werschulz, What is the complexity of elliptic systems?, J. Approx. Theory 45 (1985), no. 1, 69–84. MR 808121, DOI 10.1016/0021-9045(85)90060-7
- Arthur G. Werschulz and Henryk Woźniakowski, Are linear algorithms always good for linear problems?, Aequationes Math. 31 (1986), no. 2-3, 202–211. MR 867518, DOI 10.1007/BF02188189
- H. Woźniakowski, Information-based complexity, Annual review of computer science, Vol. 1, Annual Reviews, Palo Alto, CA, 1986, pp. 319–380. MR 876097
- H. Woźniakowski, Probabilistic setting of information-based complexity, J. Complexity 2 (1986), no. 3, 255–269. MR 922816, DOI 10.1016/0885-064X(86)90005-1 H. Woźniakowski (1986c), Complexity of integration in different settings, Proc. Optimal Algorithms (Sofia, Bulgaria), 235-240.
- Donald Ylvisaker, Designs on random fields, A survey of statistical design and linear models (Proc. Internat. Sympos., Colorado State Univ., Ft. Collins, Colo., 1973) North-Holland, Amsterdam, 1975, pp. 593–607. MR 0428662
Additional Information
- 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