Recent developments in informationbased complexity
Authors:
Edward W. Packel and Henryk Woźniakowski
Journal:
Bull. Amer. Math. Soc. 17 (1987), 936
MSC (1985):
Primary 6502, 68Q25
DOI:
https://doi.org/10.1090/S02730979198715511X
MathSciNet review:
888879
Fulltext PDF
References  Similar Articles  Additional Information

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, https://doi.org/10.1145/4221.4222

M. Atteia (1965), Fonctionsspline généralisées, C. R. Acad. Sci. Paris 216, 21492152. 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, 244249.
 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, https://doi.org/10.1137/0215026

A. Borodin (1972), Complexity classes of recursive functions and the existence of complexity gaps, J. Assoc. Comput. Mach. 19, 158174, 576. MR 321355
 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, https://doi.org/10.1080/00036818008839292

R. Holmes (1972), Rsplines in Banach spaces, I. Interpolation of linear manifolds, J. Math. Anal. Appl. 40, 547593. 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)., 361374.

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, 119. MR 445898

R. M. Karp (1979), Recent advances in probabilistic analysis of graphtheoretic algorithms, Proc. 6th Colloq. Auto. Lang, and Program., Lecture Notes in Computer Sci. 71, 338339.
 Richard M. Karp, An algorithm to solve the 𝑚×𝑛 assignment problem in expected time 𝑂(𝑚𝑛𝑙𝑜𝑔𝑛), Networks 10 (1980), no. 2, 143–152. MR 569006, https://doi.org/10.1002/net.3230100205

R. M. Karp and M. Luby (1983), MonteCarlo algorithms for enumeration and reliability problems, Proc. 24th IEEE Found. of Comp. Sci. Sympos., 5660.
 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, https://doi.org/10.1016/0885064X(85)900214

J. Kiefer (1953), Sequential minimax search for a maximum, Proc. Amer. Math. Soc. 4, 502505. 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, 495502. MR 254999

G. S. Kimeldorf and G. Wahba (1970b), Spline functions and stochastic processes, Sankhyā Ser. A 32, 173180. MR 303594

H. H. Kuo (1975), Gaussian measures in Banach spaces, Lecture Notes in Math., vol. 463, SpringerVerlag, 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, 378421. MR 303193
 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, https://doi.org/10.1016/0885064X(86)90021X

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, 154. 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, 10601062 [English transl.: Soviet Math. Dokl. 14, 11801183]. MR 326249
 A. S. Nemirovsky and D. B. Yudin, Problem complexity and method efficiency in optimization, A WileyInterscience Publication, John Wiley & Sons, Inc., New York, 1983. Translated from the Russian and with a preface by E. R. Dawson; WileyInterscience Series in Discrete Mathematics. MR 702836

S. M. Nikolskij (1950), On the problem of approximation estimate by quadrature formulae (in Russian), Uspekhi Mat. Nauk 5, 165177.

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, 2940 [English transl.: Math. Notes 19, 1723]. MR 454020
 Edward W. Packel, Linear problems (with extended range) have linear optimal algorithms, Aequationes Math. 31 (1986), no. 1, 18–25. MR 857683, https://doi.org/10.1007/BF02188168
 Edward W. Packel, Do linear problems have linear optimal algorithms?, SIAM Rev. 30 (1988), no. 3, 388–403. MR 958097, https://doi.org/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 (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, 2139. 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., 115136. MR 277069

A. Sard (1949), Best approximate integration formulas; best approximation formulas, Amer. J. Math. 71, 8091. MR 29283
 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
 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, https://doi.org/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, https://doi.org/10.1016/0885064X(86)900208
 K. Sikorski, Bisection is optimal, Numer. Math. 40 (1982), no. 1, 111–117. MR 681817, https://doi.org/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, https://doi.org/10.1016/0885064X(85)900111

A. V. Skorohod (1974), Integration in Hilbert space, SpringerVerlag, New York. MR 466482
 Steve Smale, The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 1–36. MR 590817, https://doi.org/10.1090/S027309791981148588
 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, https://doi.org/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, https://doi.org/10.1090/S027309791985153911

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), 145158, 1960, no. 5 (18), 165179 (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 5A1, pp. 14, Los Angeles. MR 144459

J. F. Traub (1964), Iterative methods for the solution of equations, PrenticeHall, Englewood Cliffs, New Jersey; reprinted by Chelsea Press, New York, 1982. MR 169356
 Joseph Frederick Traub, G. W. Wasilkowski, and H. Woźniakowski, Information, uncertainty, complexity, AddisonWesley 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. 12, 1–25. MR 742399, https://doi.org/10.1016/03043975(84)900094
 Joe Fred Traub and H. Woźniakowsi, A general theory of optimal algorithms, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New YorkLondon, 1980. ACM Monograph Series. 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, NorthHolland Publishing Co., New YorkAmsterdam, 1981. Translated from the Russian by I. I. Kotlarski; NorthHolland Series in Probability and Applied Mathematics. MR 626346

G. Wahba (1971), On the regression design problem of Sacks and Ylvisaker, Ann. Math. Statist. 42, 10351053. MR 279955
 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

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, https://doi.org/10.1016/0885064X(85)900238
 G. W. Wasilkowski, Information of varying cardinality, J. Complexity 2 (1986), no. 3, 204–228. MR 922813, https://doi.org/10.1016/0885064X(86)900026
 G. W. Wasilkowski, Optimal algorithms for linear problems with Gaussian measures, Rocky Mountain J. Math. 16 (1986), no. 4, 727–749. MR 871033, https://doi.org/10.1216/RMJ1986164727
 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, https://doi.org/10.1016/00219045(86)900432
 G. W. Wasilkowski and H. Woźniakowski, Can adaption help on the average?, Numer. Math. 44 (1984), no. 2, 169–190. MR 753951, https://doi.org/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, https://doi.org/10.1090/S00255718198206456584

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, https://doi.org/10.1016/0885064X(85)900135
 Arthur G. Werschulz, What is the complexity of elliptic systems?, J. Approx. Theory 45 (1985), no. 1, 69–84. MR 808121, https://doi.org/10.1016/00219045(85)900607
 Arthur G. Werschulz and Henryk Woźniakowski, Are linear algorithms always good for linear problems?, Aequationes Math. 31 (1986), no. 23, 202–211. MR 867518, https://doi.org/10.1007/BF02188189
 H. Woźniakowski, Informationbased 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 informationbased complexity, J. Complexity 2 (1986), no. 3, 255–269. MR 922816, https://doi.org/10.1016/0885064X(86)900051

H. Woźniakowski (1986c), Complexity of integration in different settings, Proc. Optimal Algorithms (Sofia, Bulgaria), 235240.

D. Ylvisaker (1975), Designs on random fields, A Survey of Statistical Design and Linear Models (J. N. Srivastava, ed.), NorthHolland, New York, 593607. MR 428662
Retrieve articles in Bulletin of the American Mathematical Society with MSC (1985): 6502, 68Q25
Retrieve articles in all journals with MSC (1985): 6502, 68Q25
Additional Information
DOI:
https://doi.org/10.1090/S02730979198715511X