Given a subset of the hypercube and a copy translated by s, find s

Question

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?

Answer 1

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$).

Answer 2

(Disclaimer: I read the question incorrectly; this method works when using the addition in $\mathbb{R}$, not the addition in $\mathbb{F}_2 the question asks for.)

Here is a sublinear (in $n$) randomized algorithm which runs in time $\mathcal{O}(d\log\tfrac{d}{\delta})$, failing with probability at most $\delta$. This is faster than the $\mathcal{O}(nd)$ solution mentioned above when $\log\tfrac{d}{2\delta} = o(n)$, but does not help when $d \geq \tfrac{\delta}{2} e^{\Omega(n)}$. The method simply takes advantage of the fact that if $a\sim\textrm{Unif}(A)$ and $b\sim\textrm{Unif}(B)=s+\textrm{Unif}(A)$, then $s = \mathbb{E}(b-a)$.

Algorithm: Take $k = \lceil 8\log\tfrac{2d}{\delta}\rceil$. Sample $x_1, x_2, \ldots,x_k$ independently and uniformly from $A$; similarly sample $y_1,y_2,\ldots,y_k$ independently and uniformly from $B$. Compute $\hat\mu_a = \tfrac{1}{k}(x_1+\cdots+x_k)$, $\hat\mu_b = \tfrac{1}{k}(y_1+\cdots+y_k)$, and write $\hat s = \hat\mu_b - \hat\mu_a$. Output $s^\star\in\{0,1\}^d$, where $$s_i^\star = \begin{cases}0 & \text{if }\hat s_i < \tfrac{1}{2},\\1 & \text{otherwise.}\end{cases}$$

Note: We can compute $\hat\mu_a$ and $\hat\mu_b$ in an online fashion while sampling from $A$ and $B$, but still need $\mathcal{O}(\log\tfrac{d}{\delta})$ total words of space to handle the precision needed for the computations. We also need $\mathcal{O}(d \log\tfrac{d}{\delta})$ bits of randomness.

Notation: I'll denote the $\ell^\infty$ norm by $\|x\|_\infty = \max_{i\in[d]}|x_i|$ as usual.

Proof of Correctness: Write $\mu_a = \mathbb{E}x_1$ and $\mu_b = \mathbb{E}y_1.$ If we fix a given $j\in[d]$, Hoeffding's inequality ensures that $$\mathbb{P}(|\hat\mu_{bj} - \mu_{bj}|\geq \tfrac{1}{4}) = \mathbb{P}(|\hat\mu_{aj} - \mu_{aj}|\geq \tfrac{1}{4})\leq 2e^{-8k}.$$ Via a union bound, then, we know that $$\mathbb{P}(\|\hat\mu_{b} - \mu_{b}\|_\infty\geq \tfrac{1}{4}) = \mathbb{P}(\|\hat\mu_{a} - \mu_{a}\|_\infty\geq \tfrac{1}{4})\leq 2de^{-8k}.$$

Now we can bound $$\|\hat s - s\|_\infty = \|\hat\mu_b - (\mu_a + s) - (\hat\mu_a - \mu_a)\|_\infty \leq \|\hat\mu_b-\mu_b\|_\infty + \|\hat\mu_a-\mu_a\|_\infty$$ by the triangle inequality and the fact that $\mu_b=s+\mu_a$. Thus, given our choice of $k$, $$\mathbb{P}(\|\hat s - s\|_\infty \geq \tfrac{1}{2})\leq \mathbb{P}(\|\hat \mu_b - \mu_b\|_\infty \geq \tfrac{1}{4}) + \mathbb{P}(\|\hat \mu_a - \mu_a\|_\infty \geq \tfrac{1}{4})\leq \delta.$$ Since (with probability at least $1-\delta$) our vector $\hat s$ is within $1/2$ of $s$ at each coordinate, and $s$ is a bit vector, with the same probabilistic guarantee we know the rounded solution $s^\star$ is correct.