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?

• Your Fourier approach is very nice. However, it fails when $A$ is a linear subspace spanned by some vectors $v_1,\dots,v_k$ (equivalently: there is a matrix $M$ such that $A=\{Mx : x\in \{0,1\}^{d'}\}$; or equivalently: there is a matrix $M$ such that $A=\{x : Mx=0\}$). More generally, it fails when both the indicator function of $A$ and its Fourier transform are sparse (their support is small). – D.W. Jul 10 '19 at 15:54
• @D.W. For a $d'$ dimensional subspace like $A=\{Mx \mid x\in\{0,1\}^{d'}\}$ the Fourier transform will be supported on a $d-d'$ dimensional subspace (with +-1 values). Looks like these are the extremal sets for the 'uncertainty principle'. – boinkboink Jul 10 '19 at 16:18
• When $n$ is odd you just need to add (xor) all the vectors in $A\cup B$. – Peter Taylor Jul 11 '19 at 13:21
• And if you project onto one dimension and simply count, you will recover the corresponding bit of $s$ unless the count splits 50:50, so for odd $d$ there's a simple algorithm which takes $O(nd)$. – Peter Taylor Jul 11 '19 at 13:32
• @PeterTaylor Thank you, that certainly solves it when n is odd. This can be incorporated to the second algorithm I mentioned: if there is an i such that $|D_i|$ is odd, then one can xor all the elements in this class (in A and B) to get the answer – boinkboink Jul 11 '19 at 13:57

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

(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. • I'd be interested in knowing if a$\mathcal{O}(d)$time solution is possible, or if$\mathcal{O}(d\log d)$is the best we can do. – cdipaolo Jul 15 '19 at 3:26 • Thanks! Note the plus sign in the first paragraph and the second paragraph mean different additions. – boinkboink Jul 15 '19 at 6:32 • I don’t understand how this is supposed to work. If$A=\{(0,\dots,0),(1,\dots,1)\}$, then$B=\{s,\overline s\}$, hence$\mu_a=\mu_b=(\frac12,\dots,\frac12)$irrespective of$s$. This answer seems to be conflating addition mod$2$with addition in$\mathbb R$. – Emil Jeřábek Jul 15 '19 at 7:32 • @boinkboink, maybe it would help to use$\oplus$in the question for additions in the finite field? – Peter Taylor Jul 15 '19 at 13:15 • Yep I was thinking about addition over$\mathbb{R}\$. I’ll put a disclaimer in the answer text. Thanks for the counterexample @EmilJeřábek! – cdipaolo Jul 15 '19 at 15:03