Wolfgang J. Paul
ABSTRACT
Static, descriptional complexity (program size) [16, 9] can be used to obtain lower bounds on dynamic, computational complexity (such as running time). We describe and discuss this “information-theoretic approach” in the following section. Paul introduced it in [13], to obtain restricted lower bounds on the time complexity of sorting. We use the approach here to obtain lower time bounds for on-line simulation of one abstract storage unit by another. A major goal of our work is to promote the approach.
- 1.S. O. AANDERAA, On k-tape versus (k-l)-tape real time computation, in Complexity of Computation (SIAM-AMS Proceedings, Vol. 7), R. M. Karp, Ed., American Mathematical Society, Providence, Rhode Island, 1974, pp. 75–96.Google Scholar
- 2.S. A. COOK and S. O. AANDERAA, On the minimum computation time of functions, Transactions of the American Mathematical Society, Vol. 142, August 1969, pp. 291–314.Google Scholar
- 3.M. J. FISCHER and A. L. ROSENBERG, Real-time solutions of the origin-crossing problem, Mathematical Systems Theory, Vol. 2, No. 3, September 1968, pp. 257–263.Google Scholar
- 4.P. C. FISCHER, A. R. MEYER, and A. L. ROSENBERG, Counter machines and counter languages, Mathematical Systems Theory, Vol. 2, No. 3, September 1968, pp. 265–283.Google Scholar
- 5.P. C. FISCHER, A. R. MEYER, and A. L. ROSENBERG, Real-time simulation of multihead tape units, Journal of the Association for Computing Machinery, Vol. 19, No. 4, October 1972, pp. 590–607. Google Scholar
- 6.D. JU. GRIGOR'EV, Imbedding theorems for Turing machines of different dimensions and Kolmogorov's algorithms, Soviet Mathematics, Vol. 18, No. 3, May-June 1977, pp. 588–592.Google Scholar
- 7.F. C. HENNIE, On-line Turing machine computations, IEEE Transactions on Electronic Computers, Vol. EC-15, No. 1, February 1966, pp. 35–44.Google Scholar
- 8.F. C. HENNIE and R. E. STEARNS, Two-tape simulation of multitape Turing machines, Journal of the Association for Computing Machinery, Vol. 13, No. 4, October 1966, pp. 533–546. Google Scholar
- 9.A. N. KOLMOGOROV, Three approaches to the quantitative definition of information, Problems of Information Transmission, Vol. 1, No. 1, January-March 1965, pp. 1–7. Google Scholar
- 10.S. R. KOSARAJU, Real-time simulation of concatenable double-ended queues by double-ended queues (preliminary version), Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, Atlanta, Georgia, 1979, pp. 346–351. Google ScholarDigital Library
- 11.B. L. LEONG and J. I. SEIFERAS, New real-time simulations of multihead tape units, Journal of the Association for Computing Machinery, to appear. Google Scholar
- 12.M. S. PATERSON, M. J. FISCHER, and A. R. MEYER, An improved overlap argument for on-line multiplication, in Complexity of Computation (SIAM-AMS Proceedings, Vol. 7), R. M. Karp, Ed., American Mathematical Society, Providence, Rhode Island, 1974, pp. 97–111.Google Scholar
- 13.W. J. PAUL, Kolmogorov complexity and lower bounds, Second International Conference on Fundamentals of Computation Theory, September 1979.Google Scholar
- 14.N. PIPPENGER and M. J. FISCHER, Relations among complexity measures, Journal of the Association for Computing Machinery, Vol. 26, No. 2, April 1979, pp. 361–381. Google Scholar
- 15.M. O. RABIN, Real time computation, Israel Journal of Mathematics, Vol. 1, No. 4, December 1963, pp. 203–211.Google Scholar
- 16.R. J. SOLOMONOFF, A formal theory of inductive inference. Part I, Information and Control, Vol. 7, No. 1, March 1964, pp. 1–22.Google Scholar
Index Terms
- An information-theoretic approach to time bounds for on-line computation (preliminary version)
Recommendations
Information-theoretic upper and lower bounds for statistical estimation
In this paper, we establish upper and lower bounds for some statistical estimation problems through concise information-theoretic arguments. Our upper bound analysis is based on a simple yet general inequality which we call the information exponential ...
Tighter information-theoretic generalization bounds from supersamples
ICML'23: Proceedings of the 40th International Conference on Machine LearningIn this work, we present a variety of novel information-theoretic generalization bounds for learning algorithms, from the supersample setting of Steinke & Zakynthinou (2020)—the setting of the "conditional mutual information" framework. Our development ...
Strengthened Information-theoretic Bounds on the Generalization Error
2019 IEEE International Symposium on Information Theory (ISIT)The following problem is considered: given a joint distribution P<inf>XY</inf> and an event E, bound P<inf>XY</inf> (E) in terms of P<inf>X</inf>P<inf>Y</inf> (E) (where P<inf>X</inf>P<inf>Y</inf> is the product of the marginals of P<inf>XY</inf>) and a ...
Comments