DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2018.12

Space Complexity of Two Adaptive Bitprobe Schemes Storing Three Elements

Authors: Deepanjan Kesh

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract

We consider the following set membership problem in the bitprobe model - that of storing subsets of size at most three from a universe of size m, and answering membership queries using two adaptive bitprobes. Baig and Kesh [Mirza Galib Anwarul Husain Baig and Deepanjan Kesh, 2018] proposed a scheme for the problem which takes O(m^{2/3}) space. In this paper, we present a proof which shows that any scheme for the problem requires Omega(m^{2/3}) amount of space. These two results together settle the space complexity issue for this particular problem.

Cite as

Deepanjan Kesh. Space Complexity of Two Adaptive Bitprobe Schemes Storing Three Elements. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kesh:LIPIcs.FSTTCS.2018.12,
  author =	{Kesh, Deepanjan},
  title =	{{Space Complexity of Two Adaptive Bitprobe Schemes Storing Three Elements}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{12:1--12:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.12},
  URN =		{urn:nbn:de:0030-drops-99110},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.12},
  annote =	{Keywords: Data structures, set membership problem, bitprobe model, lower bound}
}

Search Results

Documents authored by Kesh, Deepanjan

Space Complexity of Two Adaptive Bitprobe Schemes Storing Three Elements

Abstract

Cite as

Thanks for your feedback!

Could not send message