Arnold Schönhage
Abstract
For on-line random-access machines under logarithmic cost, the simple task of storing arbitrary binary inputs has nonlinear complexity. Even if all kinds of powerful internal operations are admitted and reading of storage locations is free of charge, just successively changing the storage contents for properly storing arbitrary n-bit inputs requires an average cost of order n · log*n.
- 1 AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974. Google Scholar
- 2 KATAJAINEN, J., VAN LEEUWEN, J., AND PENTTONEN, M.O. Fast simulation of Turing machines by random access machines. Rep. 837. Univ. of Turku, Finland, Oct. 1985.Google Scholar
- 3 SCrlONHAGE, A. Storage modification machines. SIAM J. Comput. 9 (1980), 490-508.Google Scholar
Index Terms
- A nonlinear lower bound for random-access machines under logarithmic cost
Recommendations
Beating the logarithmic lower bound: randomized preemptive disjoint paths and call control algorithms
Special issue: On-line algorithm part IWe consider the maximum disjoint paths problem and its generalization, the call control problem, in the on-line setting. In the maximum disjoint paths problem, we are given a sequence of connection requests for some communication network. Each request ...
A lower bound for the QRQW PRAM
SPDP '95: Proceedings of the 7th IEEE Symposium on Parallel and Distributeed ProcessingThe queue-read, queue-write (QRQW) parallel random access machine (PRAM) model is a shared memory model which allows concurrent reading and writing with a time cost proportional to the contention. This is designed to model currently available parallel ...
Lower bound for succinct range minimum query
STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of ComputingGiven an integer array A[1..n], the Range Minimum Query problem (RMQ) asks to preprocess A into a data structure, supporting RMQ queries: given a,b∈ [1,n], return the index i∈[a,b] that minimizes A[i], i.e., argmin i∈[a,b] A[i]. This problem has a ...
Comments