Saving probe bits by cube domination

We consider the problem of storing a single element from an m-element set as\ua0a binary string of optimal length, and comparing any queried string to the stored string without reading all bits. This is the one-element version of the\ua0problem of membership testing in the bit probe model, and solutions can serve\ua0as building blocks of general membership testers. Our principal contribution is\ua0the equivalence of saving probe bits with some generalized notion of domination\ua0in hypercubes. This domination variant requires that every vertex outside the\ua0dominating set belongs to a sub-hypercube, of fixed dimension, in which all\ua0other vertices belong to in the dominating set. This fixed dimension equals the\ua0number of saved probe bits. We give specific constructions showing that up to\ua0three probe bits can be ignored when m is far enough from the next larger\ua0power of 2. The main technical idea is to use low-dimensional (grid)\ua0relaxations of the problem. The design of optimal schemes remains an open\ua0problem, however one has to notice that even usual domination in hypercubes is\ua0far from being completely understood