2026-07-21T14:15:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12696 2024-03-06T10:50:36Z ddc:004 open_access

Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes Dey, Palash Radhakrishnan, Jaikumar Velusamy, Santhoshini Set membership Bit-probe model Fully-explicit data structures Adaptive data structures Error-correcting codes We consider the bit-probe complexity of the set membership problem: represent an n-element subset S of an m-element universe as a succinct bit vector so that membership queries of the form "Is x ∈ S" can be answered using at most t probes into the bit vector. Let s(m,n,t) (resp. s_N(m,n,t)) denote the minimum number of bits of storage needed when the probes are adaptive (resp. non-adaptive). Lewenstein, Munro, Nicholson, and Raman (ESA 2014) obtain fully-explicit schemes that show that s(m,n,t) = 𝒪((2^t-1)m^{1/(t - min{2⌊log n⌋, n-3/2})}) for n ≥ 2,t ≥ ⌊log n⌋+1 . In this work, we improve this bound when the probes are allowed to be superlinear in n, i.e., when t ≥ Ω(nlog n), n ≥ 2, we design fully-explicit schemes that show that s(m,n,t) = 𝒪((2^t-1)m^{1/(t-{n-1}/{2^{t/(2(n-1))}})}), asymptotically (in the exponent of m) close to the non-explicit upper bound on s(m,n,t) derived by Radhakrishan, Shah, and Shannigrahi (ESA 2010), for constant n. In the non-adaptive setting, it was shown by Garg and Radhakrishnan (STACS 2017) that for a large constant n₀, for n ≥ n₀, s_N(m,n,3) ≥ √{mn}. We improve this result by showing that the same lower bound holds even for storing sets of size 2, i.e., s_N(m,2,3) ≥ Ω(√m). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Palash Dey and Jaikumar Radhakrishnan and Santhoshini Velusamy 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.28 urn:nbn:de:0030-drops-126965 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.28 eng https://creativecommons.org/licenses/by/3.0/legalcode