Improved Bounds for Two Query Adaptive Bitprobe Schemes Storing Five\n Elements

2019/10/07 by Mirza Galib Anwarul Husain Baig, Baig, Mirza Galib Anwarul Husain, Deepanjan Kesh +1
Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #Coding theory and cryptography #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1910.03651

openalex publication_date 2019/10/07 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28

Abstract

In this paper, we study two-bitprobe adaptive schemes storing five elements.\nFor these class of schemes, the best known lower bound is m^1/2 due to Alon\nand Feige [SODA 2009]. Recently, it was proved by Kesh [FSTTCS 2018] that\ntwo-bitprobe adaptive schemes storing three elements will take at least m^2/3\nspace, which also puts a lower bound on schemes storing five elements. In this\nwork, we have improved the lower bound to m^3/4. We also present a scheme for\nthe same that takes O(m^5/6) space. This improves upon the\nO(m^18/19)-scheme due to Garg [Ph.D. Thesis] and the O(m^10/11)-scheme due\nto Baig et al. [WALCOM 2019].\n

Related

• A Two Query Adaptive Bitprobe Scheme Storing Five Elements
• An Improved Scheme in the Two Query Adaptive Bitprobe Model
• Lower Bounds for Restricted Schemes in the Two-Adaptive Bitprobe Model
• The effective entropy of next/previous larger/smaller value queries
• Set Membership with a Few Bit Probes