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?