Bulletin of the American Mathematical Society

Author(s): Edward W. Packel; Henryk Woźniakowski
Journal: Bull. Amer. Math. Soc. 17 (1987), 9-36.
MSC (1985): Primary 65-02, 68Q25
MathSciNet review: 888879
Retrieve article in: PDF

I. Adler, R. M. Karp, and R. Shamir (1983), A simplex variant solving an m × d linear program in O(min( m ², d ²)) 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

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

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-9485(e) ISSN 0273-0979(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues: 1891 - Present Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS