Information-based complexity: New questions for mathematicians

DOI10.1007/BF03024085MaRDI QIDQ751814zbMATH OpenOpenAlexWikidataFDO

Authors J. F. Traub, H. Woźniakowski

Publication date 1991

Published in The Mathematical Intelligencer (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf03024085

zbMATH Keywords

randomizationInformation-based complexityHypotheses

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 1246413
• There exists a linear problem with infinite combinatory complexity
• Recent developments in information-based complexity
• Continuous problems: optimality, complexity, tractability (invited talk)
• scientific article; zbMATH DE number 953052

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A clock synchronization problem with random delays
• Approximation of smooth periodic functions in several variables
• Bisection is not optimal on the average
• Complexity of Solving Linear Systems in Different Models of Computation
• Complexity of linear programming
• Complexity of multilinear problems in the average case setting
• Gaussian elimination is not optimal
• How to multiply matrices faster
• Matrix multiplication via arithmetic progressions
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the optimality of Krylov information
• Recent developments in information-based complexity

Cited in

(11)

• Perspectives on information-based complexity
• Computational Power of Quantum Machines, Quantum Grammars and Feasible Computation
• A refined model of computation for continuous problems
• The worst case complexity of the fredholm equation of the second kind with non-periodic free term and noise information
• There exists a linear problem with infinite combinatory complexity
• The worst case complexity of the fredholm equation with periodic free term and noisy information^∗
• The average case complexity of the Fredholm equation of second kind with free term in H^ r()
• Kolmogorov complexity and information theory. With an interpretation in terms of questions and answers
• Parallel information-based complexity of numerical integration on holder classH^s,α_M(Ω)^∗
• Average case complexity of linear multivariate problems. I: Theory
• scientific article; zbMATH DE number 446839 (Why is no real title available?)

This page was built for publication: Information-based complexity: New questions for mathematicians

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q751814)