Abstract | ||
---|---|---|
In this paper, we look into the adaptive bitprobe model that stores subsets of size at most four from a universe of size m, and answers membership queries using two bitprobes. We propose a scheme that stores arbitrary subsets of size four using O(m^{5/6}) amount of space. This improves upon the non-explicit scheme proposed by Garg and Radhakrishnan [Garg2015] which uses O(m^{16/17}) amount of space, and the explicit scheme proposed by Garg [Thesis2015] which uses O(m^{14/15}) amount of space. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1007/978-3-030-25005-8_3 | international workshop on combinatorial algorithms |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Universe,Mathematics | Journal | abs/1812.04802 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mirza Galib Anwarul Husain Baig | 1 | 1 | 1.74 |
Deepanjan Kesh | 2 | 74 | 6.53 |
Chirag Sodani | 3 | 0 | 0.34 |