7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – D.W. Jul 10 at 15:54
  • $\begingroup$ @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'. $\endgroup$ – boinkboink Jul 10 at 16:18
  • 1
    $\begingroup$ When $n$ is odd you just need to add (xor) all the vectors in $A\cup B$. $\endgroup$ – Peter Taylor Jul 11 at 13:21
  • $\begingroup$ 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)$. $\endgroup$ – Peter Taylor Jul 11 at 13:32
  • $\begingroup$ @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 $\endgroup$ – boinkboink Jul 11 at 13:57
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

(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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – cdipaolo Jul 15 at 3:26
  • $\begingroup$ Thanks! Note the plus sign in the first paragraph and the second paragraph mean different additions. $\endgroup$ – boinkboink Jul 15 at 6:32
  • 2
    $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek Jul 15 at 7:32
  • $\begingroup$ @boinkboink, maybe it would help to use $\oplus$ in the question for additions in the finite field? $\endgroup$ – Peter Taylor Jul 15 at 13:15
  • $\begingroup$ Yep I was thinking about addition over $\mathbb{R}$. I’ll put a disclaimer in the answer text. Thanks for the counterexample @EmilJeřábek! $\endgroup$ – cdipaolo Jul 15 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.