# Lower-bounding the Membership Problem in the Bitprobe Model

I am working through the following paper "Data Structures for Storing Small Sets in the Bitprobe Model" by Radhakrishnan et al. and am confused regarding one of their arguments about a lower bound.

In particular, they are trying to show that $s_A(2, m, 2) \in \Omega(m^{4/7})$. That is, the goal is to store a set $S$ of $2$ elements from a universe $U$ of size $m$ such that a query of the form "is $x \in S$" can be answered using only $2$ bit probes. The $s_A(2, m, 2)$ indicates the minimum number of bits required to answer such queries, and in particular, the scheme is allowed to be adaptive (the second probe can depend on the first one).

They begin by saying that such a scheme can be defined by three functions $a, b, c\colon [m] \to [s]$, where the query "is $x \in S$" is answered by first probing location $a(x)$ then probing locations $b(x)$ or $c(x)$ depending on the outcome of the first probe. They then go on to explain that this can be viewed as a bipartite multigraph where $G = (B = [s], C = [s], E = \{\langle b(x), c(x)\rangle : x \in [m]\})$. Lastly, they state that $E$ is naturally partitioned into sets $E_1, E_2, \ldots E_s$, where $$E_i = \{\langle b(x), c(x)\rangle : x \in [m], a(x) = i \}$$.

Now, my questions are as follows. First they make the assumption that "Each $E_i$ is a matching $\ldots$ Details Omitted". Why can this assumption be made? I can't for the life of me figure out why this needs to be the case.

My second (and more important question) is this. They provide the following example: They state that edges with the same type of label (i.e $x$ and $x'$) belong to the same matching. In their caption, they state that if such a scheme were to exist, then there are some pairs that cannot be stored (such as $x$ and $y$ on the left). This is what I don't understand. They do not provide an explanation beyond the "If it were to exist in our graph, then the underlying scheme cannot store all sets of size two. In particular, it is easy to verify that if this configuration exists, there is no way to store the set $\{x, y\}$".

I am just getting myself familiar in this area, so some of the "obvious" things may not be so obvious to me right away.

I'll only address your main question. Consider the structure for storing $\{x,y\}$. When you query $x$, you get either "left" or "right" at the first probe. Say you got "right". Then the right endpoint of the edge $x$ must be 1 (we use the convention that the output is the last bit read, see the paper). When querying $x'$, we read the same first bit, and so the right endpoint of the edge $x'$ must be 0. This means that the left endpoint of $y$ must be 1. This means that when querying $w'$, the first bit read must be "right". But then when we query $w$, we read the right endpoint of the edge $w$ which is 1.
Suppose now that you got "left" in the first probe of $x$. Then the left endpoint must be 1, and so the first probe of $y'$ must be "right". Therefore the right endpoint of $y$ must be 1, and so the first probe of $z'$ must be "left". But then when we query $z$, we answer the left endpoint of $z$ which is 1. In both cases we have reached a contradiction.
• I have been working through this proof, without much luck during the past week. I tried leaving it aside for a few days and work on something else, then coming back to it after, though it did not help. I am able to verify most of the statements mathematically, but I feel like I lack the intuition behind what some of the variables are for (too many nested things perhaps). I was wondering if you could provide some insight into why the second picture cannot be stored, and perhaps what the $\Delta_{\alpha}$ stands for intuitively. – user340082710 Jun 9 '14 at 1:30