Brief History
Precursors to IBC may be found in the 1950s by Kiefer, Sard, and Nikolskij. In 1959 Traub had the key insight that the optimal algorithm and the computational complexity of solving a continuous problem depended on the available information. He applied this insight to the solution of nonlinear equations which started the area of optimal iteration theory. This research was published in the 1964 monograph Iterative Methods for the Solution of Equations.
The general setting for information-based complexity was formulated by Traub and Woźniakowski in 1980 in A General Theory of Optimal Algorithms. For a list of more recent monographs and pointers to the extensive literature see To Learn More below.
Read more about this topic: Information-based Complexity
Famous quotes containing the word history:
“When the history of this period is written, [William Jennings] Bryan will stand out as one of the most remarkable men of his generation and one of the biggest political men of our country.”
—William Howard Taft (1857–1930)
“The history of any nation follows an undulatory course. In the trough of the wave we find more or less complete anarchy; but the crest is not more or less complete Utopia, but only, at best, a tolerably humane, partially free and fairly just society that invariably carries within itself the seeds of its own decadence.”
—Aldous Huxley (1894–1963)