Miklos Ajtai
STOC 1998
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 1998
Miklos Ajtai, N. Alon, et al.
FOCS 1992
Miklos Ajtai, Ronald Fagin, et al.
STOC 1998
Miklos Ajtai, Nimrod Megiddo, et al.
FOCS 1995