1
$\begingroup$

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: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.

Improve this question
$\endgroup$
2
$\begingroup$

First, the reason why the authors had to omit so many details is that the paper was published in a conference (SOCG) with a strict page limit. When you publish your paper, please provide a full version on your website with all the proofs. In my area usually the full details are in an appendix which is not available from the conference website since back in the day, the proceedings were printed and so a strict page limit had to be enforced. Nowadays many proceedings are online only and then there is no page limit, but it seems that your paper dates from before that period.

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.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks! Your answer is crystal clear. I had forgotten a few of the underlying assumptions (like the convention that you pointed out), but now makes perfect sense. I need to get better at reading research papers. $\endgroup$ – user340082710 May 28 '14 at 20:53
  • $\begingroup$ Actually, the same type of argument does not seem to work for the second picture. Unless I have misunderstood something, I cannot get a contradictions in both directions like you have done. $\endgroup$ – user340082710 May 28 '14 at 21:54
  • 1
    $\begingroup$ @ZacharyFrenette Clearly something is missing - perhaps not all the required information is there, or perhaps the required contradiction is more complicated. Part of the art of reading papers is being able to work through such issues yourself. I suggest you read the complete proof, and at the point where they invoke Figure 1(b), see if you can find some contradiction. The fact that they need 3 pairs suggests the use of the pigeonhole principle. $\endgroup$ – Yuval Filmus May 28 '14 at 23:12
  • $\begingroup$ 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. $\endgroup$ – user340082710 Jun 9 '14 at 1:30
  • $\begingroup$ I did manage to figure out why the assumption of a matching is required, but I haven't been able to fill these details out yet. I was able to work through the upper bound proofs in the paper, but I am finding the lower-bound ones to be much more difficult to parse through. $\endgroup$ – user340082710 Jun 9 '14 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.