# Using Yao's principle to find a lower bound

This is a HW question, so I'm not expecting any answers, just a general guidance/help.

Definition. Given $$\underset{\neq0}{\underbrace{s}}\in\left\{ 0,1\right\} ^{n}$$, a function $$f:\left\{ 0,1\right\} ^{n}\to\left\{ 0,1\right\} ^{n}$$ will be called s-difference-preserving if for all $$x,y\in\left\{ 0,1\right\} ^{n}$$ s.t. $$x\neq y$$: $$x\oplus y=s\iff f\left(x\right)=f\left(y\right)$$ (where $$\oplus$$ is the bitwise xor operation).

Given a difference-preserving (that is, there exists such s so it is s-difference-preserving) function $$f$$, we talk about algorithms that find such $$s$$.

We need to prove that every such random (las-vegas) algorithm worst case (w.c. input) average (on the randomness of the algorithm) complexity is $$\Omega\left(\sqrt{2^{n}}\right)$$. Where by complexity, we talk about query-complexity. That is, how many times we need to query f, to find a value for an input $$x$$ - that is, find $$f\left(x\right)$$.

What I know and tried so far:

I assume this is a classic problem for Yao's principle.
So I want to find a distribution, and an optimal deterministic algorithm for it (optimal on average, on that distribution), such that its query-complexity is \Omega\left(\sqrt{2^{n}}\right) on average on that distribution.

Given an $$s$$, it's easy to create an s-difference-preserving function, since any $$s$$ defines a partition of pairs on $$\left\{ 0,1\right\} ^{n}$$. So we just need to choose a different value for every pair $$x,y$$ s.t. $$x\oplus y=s$$.

I also know $$f\left(0\right)=f\left(s\right)$$, and that to find $$s$$ for a fuction, it's enough to find a pair $$x,y$$ s.t. $$f\left(x\right)=f\left(y\right)$$, and then calculate $$x\oplus y$$.

I thought of defining $$\forall i\in\left[\sqrt{2^{n}}\right]:\ s_{i}=i\cdot\sqrt{2^{n}}-1$$. And create $$s_{i}$$-difference-preserving function $$\forall i\in\left[\sqrt{2^{n}}\right]$$.

Define a uniform distribution on them and have the deterministic algorithm check the values of every $$s_{i}$$. This is done in $$\sqrt{2^{n}}$$ queries on average.
But I don't know how to prove this algorithm is optimal for that distribution. Furthermore, I suspect it isn't, since then I would be able to do the same with $$s_{i},\ \forall i\in\left[2^{n}\right]$$ and “prove” a lower bound of $$2^{n}$$ which is probably not true.

I would love any help with this.
Also, not as part of the HW, but because I'm interested (these are questions we don't need to submit a solution to), can you think of any deterministic algorithm for the general problem? can you think of any monte carlo random algorithm (with 0.5 chance of success)?

I hope this is not too long, and written clearly enough. Would appreciate any help. Thanks!

Suppose that there exists a Las Vegas algorithm $$A^f$$ asking $$q(n)=o\big(2^{n/2}\big)$$ queries. Let $$Q_f\subseteq\{0,1\}^n$$ be the random variable which denotes the set of queries raised by the algorithm with oracle $$f$$.
Sample $$f$$ from the uniform distribution over the collection of all difference preserving functions, and choose $$s\in\{0,1\}^n$$ uniformly at random, both independently from your algorithm's coins. Let us now ask what is the probability that there exists $$g,g':\{0,1\}^n\rightarrow\{0,1\}^n$$ such that $$g,g'$$ agrees with $$f$$ on $$Q_f$$, $$g$$ is $$s$$-difference preserving, and $$g'$$ is not. We denote this probability by $$p_A$$. Note that if $$p_A>0$$ then your algorithm cannot respond correctly on all inputs, since there exists $$f,s$$ such that $$f|_{Q_f}$$ has both $$s$$-preserving and non $$s$$-preserving extensions.
If $$f|_{Q_f}$$ does not have an $$s$$-preserving extension, then either there exists $$x\in Q_f$$ such that $$x\oplus s\in Q_f$$, or we have $$x,y\in Q_f$$ with $$f(x)=f(y)$$. For the first case, Note that $$x\oplus s$$ is uniformly distributed over $$\{0,1\}^n$$ and independent of $$Q_f$$, thus the probability that there exists such $$x$$ is bounded by $$\sum\limits_{x\in Q_f}\frac{|Q_f|}{2^n}\le\frac{q^2(n)}{2^n}=o(1)$$. A similar bound is obtained for finding a collision for a random $$f$$ (the preimage of any element in the range of $$f$$ is of size 2). Additionally, $$f$$ is not $$s$$ preserving with probability $$\ge\frac{1}{2^n}$$, so we can also (with high probability) find a non $$s$$ difference preserving extension for $$f$$.
• Thanks for your answer! I'm not sure why there exists such an $x\in Q_{f}$ if $f|_{Q_{f}}$ doesn't have the extension. What about the case where there exists $x,y\in Q_{f}$ s.t. $f\left(x\right)=f\left(y\right)$ but $x\oplus y\neq s$ ? – Ungoliant Nov 4 '18 at 21:54
• Also, unless I'm mistaken, that $f|_{Q_{f}}$ extension that is not s-preserving, should be still preserving for another s, as our algorithms only receive preserving functions, and need to find their s. – Ungoliant Nov 4 '18 at 22:04
• I edited to make $f$ random as well, which should answer your questions. – Ariel Nov 4 '18 at 22:46
• Thanks! I'm still wondering. If there exists $x,y\in Q_{f}$ s.t. $f\left(x\right)=f\left(y\right)$ we can't extend it for any s. What if $Q_{f}$ always contain such elements? In fact, it seems to me almost a requirement for the algorithm to decide... – Ungoliant Nov 4 '18 at 22:54
• $f$ is a random difference preserving function. Think of it as choosing $u\in\{0,1\}^n$ at random and then choosing, for each $x\in\{0,1\}^n$, a random value for $f(x),f(x\oplus u)$. Let $Q_f^i$ where $1\le i\le q(n)$ be the set of the first $i$ queries raised by the algorithm, and let $j$ be the minimal index such that $Q_f^j$ contains a collision. Note that $Q_f^{j-1}$ is independent of $u$, hence the probability of hitting $x\oplus u$ for some $x\in Q_f^{j-1}$ in the $j$'th iteration is bounded by $\frac{|Q_f^{j-1}|^2}{2^n}$. – Ariel Nov 5 '18 at 17:30