Conference paper
Determinism versus non-determinism for linear time RAMs
Miklos Ajtai
STOC 1999
Let L be the set consisting of the first q positive integers. We prove in this paper that there does not exist a data structure for representing an arbitrary subset A of L which uses poly (|A|) cells of memory (where each cell holds c log q bits of information) and which the predecessor in A of an arbitrary x≦q can be determined by probing only a constant (independent of q) number of cells. Actually our proof gives more: the theorem remains valid if this number is less than ε log log q, that is D. E. Willard's algorithm [2] for finding the predecessor in O(log log q) time is optimal up to a constant factor. © 1988 Akadémiai Kiadó.
Miklos Ajtai
STOC 1999
Miklos Ajtai
STOC 1998
Miklos Ajtai, Ronald Fagin, et al.
STOC 1998
Miklos Ajtai
FOCS 1999