Name
Abstract | ||
|---|---|---|
In the adaptive bitprobe model, consider the following set membership problem - store subsets of size at most two from an universe of size m, and answer membership queries using two bitprobes. Radhakrishnan et al. [3] proposed a scheme for the problem which takes O(m(2/3)) amount of space, and conjectured that this is also the lower bound for the problem. We propose a proof of the lower bound for the problem, but for a restricted class of schemes. This proof hopefully makes progress over the ideas proposed by Radhakrishnan et al. [3] and [4] towards the conjecture. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/978-3-030-11509-8_5 | ALGORITHMS AND DISCRETE APPLIED MATHEMATICS, CALDAM 2019 |
Keywords | DocType | Volume |
Data structures, Bitprobe model, Adaptive scheme, Lower bound | Conference | 11394 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Deepanjan Kesh | 1 | 74 | 6.53 |
| Vidya Sagar Sharma | 2 | 0 | 0.34 |