<p>Here is an <span class="math-container">$O(nd)$</span> time randomized solution.</p>

<p>We will use the shifting (aka compression) technique from combinatorics, in a seemingly new algorithmic way, which I have never seen done before (see <a href="https://gilkalai.wordpress.com/2008/10/06/extremal-combinatorics-iv-shifting/" rel="nofollow noreferrer">this post</a> for the definition of the compression technique).</p>

<p>Let us define a partial order on <span class="math-container">$\{0,1\}^d$</span> called the <em>set inclusion partial order</em>, denoted <span class="math-container">$\preceq$</span>, as so: Two strings <span class="math-container">$x,y$</span> satisfy <span class="math-container">$x\preceq y$</span> if <span class="math-container">$x_i = 1 \implies y_i = 1$</span> for all <span class="math-container">$i\in[d]$</span>.</p>

<p>A subset <span class="math-container">$S\subseteq\{0,1\}^d$</span> is called downward closed, or downset for short, if <span class="math-container">$y\in S \land x\preceq y\implies x\in S$</span>.</p>

<p>Intuitively, we will morph <span class="math-container">$A$</span> and <span class="math-container">$B$</span> into downsets a dimension at a time after which it will be clear which elements <span class="math-container">$x$</span> of <span class="math-container">$A$</span> are the "pairs" of which elements <span class="math-container">$x+s\in B$</span>; this evidently will reveal <span class="math-container">$s$</span>.</p>

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

<p>The algorithm will proceed in <span class="math-container">$d$</span> rounds numbered <span class="math-container">$i=1,\ldots,d$</span>. In round <span class="math-container">$i$</span>, we do the following. Let <span class="math-container">$I= [d]\setminus \{i\}$</span> and partition <span class="math-container">$A'$</span> and <span class="math-container">$B'$</span> into equivalence classes according to coordinates <span class="math-container">$I$</span> 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 <span class="math-container">$i$</span> (there is always a bijection between the left and right parts of the pairs as we'll see during this inductive argument).</p>

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

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

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

<p><b>Claim 1:</b> At the end of the <span class="math-container">$d$</span>th iteration, the left part of <span class="math-container">$A'$</span>, i.e., <span class="math-container">$\{w\mid (w,x)\in  A'\}$</span> forms a downset. Likewise for <span class="math-container">$B'$</span>.</p>

<p><b>Claim 2:</b> These two downsets are equal to each other, i.e., <span class="math-container">$\{w\mid (w,x)\in A' \} = \{w\mid (w,x)\in B' \}$</span>.</p>

<p>Now that we have <span class="math-container">$\{w\mid (w,x)\in A' \} = \{w\mid (w,x)\in B' \}$</span>, we have a natural bijection <span class="math-container">$b$</span> between <span class="math-container">$A'$</span> and <span class="math-container">$B'$</span>. One can see this bijection maps <span class="math-container">$(w,x) \in A'$</span> to <span class="math-container">$(w, x+s) \in B'$</span>, so it directly reveals <span class="math-container">$s$</span>.</p>

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

CC BY-SA 4.0
2019-07-11T19:20:14.413Z
2019-07-12T19:58:25.750Z
2019-07-12T19:58:25.750Z
boinkboink
<p>(<em>Disclaimer:</em> I read the question incorrectly; this method works when using the addition in <span class="math-container">$\mathbb{R}$</span>, not the addition in $\mathbb{F}_2 the question asks for.)</p>

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

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

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

<p><strong>Notation:</strong> I'll denote the <span class="math-container">$\ell^\infty$</span> norm by <span class="math-container">$\|x\|_\infty = \max_{i\in[d]}|x_i|$</span> as usual.</p>

<p><strong>Proof of Correctness:</strong> Write <span class="math-container">$\mu_a = \mathbb{E}x_1$</span> and <span class="math-container">$\mu_b = \mathbb{E}y_1.$</span> If we fix a given <span class="math-container">$j\in[d]$</span>, Hoeffding's inequality ensures that <span class="math-container">$$\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}.$$</span> Via a union bound, then, we know that <span class="math-container">$$\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}.$$</span></p>

<p>Now we can bound
<span class="math-container">$$\|\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$$</span> by the triangle inequality and the fact that <span class="math-container">$\mu_b=s+\mu_a$</span>. Thus, given our choice of <span class="math-container">$k$</span>, <span class="math-container">$$\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.$$</span> Since (with probability at least <span class="math-container">$1-\delta$</span>) our vector <span class="math-container">$\hat s$</span> is within <span class="math-container">$1/2$</span> of <span class="math-container">$s$</span> at each coordinate, and <span class="math-container">$s$</span> is a bit vector, with the same probabilistic guarantee we know the rounded solution <span class="math-container">$s^\star$</span> is correct.</p>

CC BY-SA 4.0
2019-07-15T03:26:16.220Z
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
CC BY-SA 4.0
2019-07-15T06:32:48.920Z
Thanks! Note the plus sign in the first paragraph and the second paragraph mean different additions.
boinkboink
CC BY-SA 4.0
2019-07-15T07:32:55.140Z
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
CC BY-SA 4.0
2019-07-15T13:15:50.540Z
@boinkboink, maybe it would help to use $\oplus$ in the question for additions in the finite field?
Peter Taylor
CC BY-SA 4.0
2019-07-15T15:03:24.740Z
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
CC BY-SA 4.0
2019-07-15T03:23:26.587Z
2019-07-15T15:07:11.437Z
2019-07-15T15:07:11.437Z
cdipaolo
<p><b>Problem:</b> Suppose we are given an <span class="math-container">$n$</span> element subset <span class="math-container">$A\subseteq\{0,1\}^d$</span> of the <span class="math-container">$d$</span> dimensional hypercube and a translated copy <span class="math-container">$B= A+s$</span> by some secret <span class="math-container">$s\in\{0,1\}^d$</span>. Find <span class="math-container">$s$</span> as fast as possible in randomized RAM model with say <span class="math-container">$d$</span>-bit wide words. Here we think of bit strings as elements of <span class="math-container">$\mathbb{F}_2^d$</span> 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.)</p>

<hr>

<p>I have <s>3</s> 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.</p>

<blockquote>
  <p>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)</p>
</blockquote>

<hr>

<p><b>Naive solution</b></p>

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

<hr>

<p><b>A better solution:</b></p>

<p>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 <span class="math-container">$S\in[d]$</span>. Partition <span class="math-container">$A=\{x^1,x^2,\ldots,x^n\}$</span> into <span class="math-container">$2^{|S|}$</span> equivalence classes according to <span class="math-container">$x_S$</span>. Here subscript means restricting <span class="math-container">$x$</span> to those coordinates in <span class="math-container">$S$</span>. Denote for <span class="math-container">$v\in\{0,1\}^S$</span>, the class of <span class="math-container">$v$</span> as <span class="math-container">$C_v = \{x\in A\mid x_S = v\}$</span>. For <span class="math-container">$v\in\{0,1\}^S$</span>, let <span class="math-container">$m_v = |C_v|$</span>. Now let us partition <span class="math-container">$A$</span> into equivalence classes according to <span class="math-container">$m_{x_S}$</span> this time. Denote for an integer <span class="math-container">$i\in[n]$</span> the class of <span class="math-container">$i$</span> as</p>

<p><span class="math-container">$$ D_i = \{x\in A\mid m_{x_S} = i\}.$$</span></p>

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

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

<hr>

<p>The above solution will not provide any improvements when <span class="math-container">$A$</span> 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.</p>

<hr>

<p><b>A Fourier theoretic approach:</b></p>

<p>Lets not try to learn <span class="math-container">$s$</span> 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 <span class="math-container">$\{0,1\}^d$</span> as well as the corresponding indicator functions. We have </p>

<p><span class="math-container">$$\hat{A}(u) = \hat{B}(u)(-1)^{\langle u, s\rangle}$$</span></p>

<p>If we pick a random <span class="math-container">$u\in\{0,1\}^d$</span>, by the above equation in linear time we will learn 1 bit of information about <span class="math-container">$s$</span>, <b>unless</b> <span class="math-container">$\hat{A}(u) = 0$</span>.</p>

<p><s>Note that this already solves the problem when <span class="math-container">$d\gg \log n$</span> due to the uncertainty principle in Fourier analysis: it will imply that at most <span class="math-container">$2^d/n$</span> Fourier coefficients are zero. Therefore the hardest case is when <span class="math-container">$d\approx \log n$</span>.</s></p>

<p>What can we do in this case?</p>

<p><b>Question 2:</b> What is the randomized RAM complexity of this problem?</p>

<p><b>Question 3:</b> What is the quantum complexity?</p>

CC BY-SA 4.0
2019-07-10T15:54:08.097Z
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.
CC BY-SA 4.0
2019-07-10T16:18:11.373Z
@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
CC BY-SA 4.0
2019-07-11T13:21:14.170Z
When $n$ is odd you just need to add (xor) all the vectors in $A\cup B$.
Peter Taylor
CC BY-SA 4.0
2019-07-11T13:32:08.263Z
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
CC BY-SA 4.0
2019-07-11T13:57:22.867Z
@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
CC BY-SA 4.0
2019-07-11T14:41:06.277Z
@PeterTaylor I missed the last part of your second comment. How does $d$ being odd help? As far as I can see, all the counts split 50:50 for e.g. $A=\{(0,0,\dots,0),(1,1,\dots,1)\}$ irrespective of the parity of the dimension.
Emil Jeřábek
CC BY-SA 4.0
2019-07-11T14:44:31.000Z
@EmilJeřábek, you're quite right: the last clause of my second comment is nonsense. It's if $n$ is odd that the counts are guaranteed not to split 50:50, but in that case the first comment gives a better solution.
Peter Taylor
CC BY-SA 4.0
2019-07-11T19:44:22.097Z
Here is the contest link. It's problem H in the given link http://codeforces.com/gym/100965/attachments/download/4261/20092010-petrozavodsk-winter-training-camp-moscow-su-unpredictable-se-old-st-contest-en.pdf
boinkboink
CC BY-SA 4.0
2020-02-23T03:24:12.430Z
At the least, you have to be careful what you mean by "find $s$", since e.g. $A$ and $B$ are the whole hypercube, every point of the hypercube is an acceptable value of $s$.  So in that case, just listing all the valid solutions requires $2^d$ time.
Dale
<quantum-computing><time-complexity><boolean-functions><fourier-analysis><analysis-of-algorithms>
Given a subset of the hypercube and a copy translated by s, find s
boinkboink
# Given a subset of the hypercube and a copy translated by s, find s

(Asked by: username_0 on 2019-07-10)

**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?

**Tags:** quantum-computing, time-complexity, boolean-functions, fourier-analysis, analysis-of-algorithms

> **Comments:**
> **username_1**: 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).  
> **username_0**: @username_1 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'.  
> **username_2**: When $n$ is odd you just need to add (xor) all the vectors in $A\cup B$.  
> **username_2**: 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)$.  
> **username_0**: @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  
> **username_3**: @PeterTaylor I missed the last part of your second comment. How does $d$ being odd help? As far as I can see, all the counts split 50:50 for e.g. $A=\{(0,0,\dots,0),(1,1,\dots,1)\}$ irrespective of the parity of the dimension.  
> **username_2**: @EmilJeřábek, you're quite right: the last clause of my second comment is nonsense. It's if $n$ is odd that the counts are guaranteed not to split 50:50, but in that case the first comment gives a better solution.  
> **username_0**: Here is the contest link. It's problem H in the given link http://codeforces.com/gym/100965/attachments/download/4261/20092010-petrozavodsk-winter-training-camp-moscow-su-unpredictable-se-old-st-contest-en.pdf  
> **username_4**: At the least, you have to be careful what you mean by "find $s$", since e.g. $A$ and $B$ are the whole hypercube, every point of the hypercube is an acceptable value of $s$.  So in that case, just listing all the valid solutions requires $2^d$ time.  

---

## 2 answers

### Answer by username_0 on 2019-07-11. Score: 0 | Accepted answer

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](https://gilkalai.wordpress.com/2008/10/06/extremal-combinatorics-iv-shifting/) 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 by username_5 on 2019-07-15. Score: 0

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

> **Comments:**
> **username_5**: 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.  
> **username_0**: Thanks! Note the plus sign in the first paragraph and the second paragraph mean different additions.  
> **username_3**: 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$.  
> **username_2**: @username_0, maybe it would help to use $\oplus$ in the question for additions in the finite field?  
> **username_5**: Yep I was thinking about addition over $\mathbb{R}$. I’ll put a disclaimer in the answer text. Thanks for the counterexample @EmilJeřábek!  

---

