Given a subset of the hypercube and a copy translated by s, find s Problem: Suppose we are given an $n$ element subset $A\subseteq\{0,1\}^d$ of the $d$ dimensional hypercube and a translated copy $B= A+s$ by some secret $s\in\{0,1\}^d$. Find $s$ as fast as possible in randomized RAM model with say $d$-bit wide words. Here we think of bit strings as elements of $\mathbb{F}_2^d$ and addition is modulo 2, namely the xor operation. (Note that even though we receive both A and B, we are not told which element is a translated version of which.)



I have 3 4 questions regarding this problem. I have encountered this question in a competitive programming (practice) contest years back. Now revisiting this question, it really looks like it originated from some tcs related question.


  Has anyone seen this or a related problem in their research? Does this relate to any PCP or property testing related constructions? (Or Simon's problem in any way)




Naive solution

Fix an element $a_0\in A$ and for each element $x\in B$, guess that $s=x-a_0$ and verify this guess in linear time by computing $A+s$ and comparing it against $B$ (we can then compare $A+s$ and $B$ in linear time by, say, hashing as we are assuming $d$-bit wide words).
This gives us an $O(n^2)$ time algorithm.



A better solution:

Here is a solution that does much better for most inputs (which allowed me to pass the test cases during the contest). Pick a random subset of $S\in[d]$. Partition $A=\{x^1,x^2,\ldots,x^n\}$ into $2^{|S|}$ equivalence classes according to $x_S$. Here subscript means restricting $x$ to those coordinates in $S$. Denote for $v\in\{0,1\}^S$, the class of $v$ as $C_v = \{x\in A\mid x_S = v\}$. For $v\in\{0,1\}^S$, let $m_v = |C_v|$. Now let us partition $A$ into equivalence classes according to $m_{x_S}$ this time. Denote for an integer $i\in[n]$ the class of $i$ as

$$ D_i = \{x\in A\mid m_{x_S} = i\}.$$

Now take the smallest nonempty class $i^* = \arg\min_i |D_i|$. If we pick $a_0$ from this class, we just need to make $|D_{i^*}|$ guesses as to what element to pair $a_0$ with inside $B$. Therefore the runtime becomes $n|D_{i^*}|$.

An idea: What if we pick a random full rank matrix $M\in\mathbb{F}_2^{d\times d}$ and transform $A$ by $M$ first, does this ensure that $\mathbb{E}_{M,S} |D_{i^*}|$ is small for any $A$? Note that for $x^1, x^2\in A$ we have $(Mx^1)_S = (Mx^2)_S$ iff $(M(x^1+s))_S = (M(x^2+s))_S$



The above solution will not provide any improvements when $A$ is a subcube. Though, in this case we can easily solve it by other observations. In general I am unable to think of hard instances to this problem and suspect there should be a provably efficient solution for all inputs.



A Fourier theoretic approach:

Lets not try to learn $s$ all at once; that way we make no measurable progress up until we actually solve the problem. How about we try to learn s bit by bit. I will use A,B to denote the subsets of $\{0,1\}^d$ as well as the corresponding indicator functions. We have 

$$\hat{A}(u) = \hat{B}(u)(-1)^{\langle u, s\rangle}$$

If we pick a random $u\in\{0,1\}^d$, by the above equation in linear time we will learn 1 bit of information about $s$, unless $\hat{A}(u) = 0$.

Note that this already solves the problem when $d\gg \log n$ due to the uncertainty principle in Fourier analysis: it will imply that at most $2^d/n$ Fourier coefficients are zero. Therefore the hardest case is when $d\approx \log n$.

What can we do in this case?

Question 2: What is the randomized RAM complexity of this problem?

Question 3: What is the quantum complexity?
Here is an $O(nd)$ time randomized solution.

We will use the shifting (aka compression) technique from combinatorics, in a seemingly new algorithmic way, which I have never seen done before (see this post for the definition of the compression technique).

Let us define a partial order on $\{0,1\}^d$ called the set inclusion partial order, denoted $\preceq$, as so: Two strings $x,y$ satisfy $x\preceq y$ if $x_i = 1 \implies y_i = 1$ for all $i\in[d]$.

A subset $S\subseteq\{0,1\}^d$ is called downward closed, or downset for short, if $y\in S \land x\preceq y\implies x\in S$.

Intuitively, we will morph $A$ and $B$ into downsets a dimension at a time after which it will be clear which elements $x$ of $A$ are the "pairs" of which elements $x+s\in B$; this evidently will reveal $s$.

For reasons which will be clear let $A'=\{(x,x)\mid x\in A\}$ and $B' = \{(x,x)\mid x\in B\}$; we will modify only the left items in these pairs $(x,x)$ and the right items are fixed and only there so we can keep track of the original labels. When I say left $i$th coordinate of $(w,x)\in A'$ it will refer to the $i$th coordinate of the string on the left pair element, that is $w$.

The algorithm will proceed in $d$ rounds numbered $i=1,\ldots,d$. In round $i$, we do the following. Let $I= [d]\setminus \{i\}$ and partition $A'$ and $B'$ into equivalence classes according to coordinates $I$ of the left pair element. It will be clear soon each nonempty class has either 1 or 2 elements depending on the last unfixed left coordinate $i$ (there is always a bijection between the left and right parts of the pairs as we'll see during this inductive argument).

Here is an example: Let $i=1$. Consider the class 
$C_u = \{(w,x)\in A' \mid w_I = u\}$. In each iteration, there will be a bijection between the left parts and right parts, so it remains to specify the first bit of $w$. Either both $(0u,\cdot), (1u,\cdot)$ are in $C_u$ or just one of them or none (we discard empty classes). This way among nonempty classes, the size is either 1 or 2.

The classes of size 2 are already good, don't touch them; no matter what $s$ is in the $i$th coordinate, they will work okay. The classes of size 1 either have $w_i=0$ or $w_i=1$. If the number of $w_i=0$ classes of $A'$ is different than the number of $w_i=1$ classes of $A'$, then we already know what $s_i$ must be (using the fact that $B$ is a translated version of $A$), so if the number of $w_i=0$ classes of $A'$ is equal to number of $w_i=1$ classes of $B'$, then flip the left $i$th coordinate of each element in $B'$, otherwise do nothing.

Now in both $A'$ and $B'$ set the left $i$th coordinate of the $w_i=1$ classes to 0. This is called a down-shift operation, as we gradually make the sets monotone.
This is the end of $i$th iteration.

Claim 1: At the end of the $d$th iteration, the left part of $A'$, i.e., $\{w\mid (w,x)\in  A'\}$ forms a downset. Likewise for $B'$.

Claim 2: These two downsets are equal to each other, i.e., $\{w\mid (w,x)\in A' \} = \{w\mid (w,x)\in B' \}$.

Now that we have $\{w\mid (w,x)\in A' \} = \{w\mid (w,x)\in B' \}$, we have a natural bijection $b$ between $A'$ and $B'$. One can see this bijection maps $(w,x) \in A'$ to $(w, x+s) \in B'$, so it directly reveals $s$.

How to implement each iteration in $O(n)$ time: We have a set of items of size $n$ that we need to partition with respect to a $d-1$ bit key (corresponding to $x_I$ for $I$ defined above) in each iteration. This we can do $O(n)$ randomized time by hashing, or $O(nd/\log n)$ deterministic time by bucketing (bucketing can be done in $O(n)$ time but $2^d$ space which could be excessive, instead we "radix it" by $\log n$).