Information-based complexity: New questions for mathematicians

DOI10.1007/BF03024085zbMath0715.68031OpenAlexW1974897382WikidataQ66459661 ScholiaQ66459661MaRDI QIDQ751814

Henryk Woźniakowski, J. F. Traub

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 of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Perspectives on information-based complexity, The average case complexity of the Fredholm equation of second kind with free term in \(H^ r(\Gamma)\), Parallel information-based complexity of numerical integration on holder classH^s,α_M(Ω)^∗, Average case complexity of linear multivariate problems. I: Theory, The worst case complexity of the fredholm equation of the second kind with non-periodic free term and noise information, The worst case complexity of the fredholm equation with periodic free term and noisy information^∗, A refined model of computation for continuous problems, Computational Power of Quantum Machines, Quantum Grammars and Feasible Computation

Cites Work

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