这是一份durham杜伦大学MATH2011-WE01/MATH30120-WE01/MATH3401-WE01作业代写的成功案例
Finally, we define algorithm $A^{\prime \prime}$. On input $y=f(x)$, the algorithm selects $j \in{1, \ldots, \ell}$ with probability $2^{-2 j+1}$ (and halts with no output otherwise). It invokes the preceding implementation of algorithm $A^{\prime}$ on input $y$ with parameter $\varepsilon \stackrel{\text { def }}{=} 2^{-j-1} / \ell$ and retums whatever $A^{\prime}$ does. The expected running time of $A^{\prime \prime}$ is
$$
\sum_{j=1}^{\ell} 2^{-2 j+1} \cdot O\left(\frac{n^{2}}{\left(2^{-j-1} / \ell\right)^{2}}\right) \cdot\left(t_{G}(n)+\log \left(n \cdot 2^{j+1} \ell\right)\right)=O\left(n^{2} \cdot \ell^{3}\right) \cdot t_{G}(n)
$$
(assuming $t_{G}(n)=\Omega(\ell \log n)$ ). Letting $i \leq \ell$ be an index satisfying Claim $2.5 .4 .1$ (and letting $S_{n}$ be the corresponding set), we consider the case in which $j$ (selected by $A^{\prime \prime}$ ) is greater than or equal to $i$. By Claim 2.5.4.2, in such a case, and for $x \in S_{n}$, algorithm $A^{\prime}$ inverts $f$ on $f(x)$ with probability at least $\frac{1}{2}$. Using $i \leq \ell$ $\left(=\log {2}(1 / \varepsilon(n))\right)$, we get $$ \begin{aligned} \operatorname{Pr}\left[A^{\prime \prime}\left(f\left(U{n}\right)\right)=U_{n}\right] & \geq \operatorname{Pr}\left[U_{n} \in S_{n}\right] \cdot \operatorname{Pr}[j \geq i] \cdot \frac{1}{2} \
& \geq 2^{i-1} \varepsilon(n) \cdot 2^{-2 i+1} \cdot \frac{1}{2} \
& \geq \varepsilon(n) \cdot 2^{-\ell} \cdot \frac{1}{2}=\frac{\varepsilon(n)^{2}}{2}
\end{aligned}
$$
The proposition follows.
MATH43220-WE01/MATH3341-WE01/MATH4031-WE01 COURSE NOTES ：
Let $\left{G_{n}\right}_{n \in \mathbb{N}}$ be a family of $d$-regular graphs, so that $G_{n}$ has vertex set ${0,1}^{n}$ and self-loops at every vertex. Consider a labeling of the edges incident to each vertex (using the labels $1,2, \ldots, d$ ). Define $g_{l}(x)$ to be the vertex reachable from vertex $x$ by following the edge labeled $l$. Let $f:{0,1}^{} \rightarrow{0,1}^{}$ be a $1-1$ length-preserving function, and let $\lambda$ denote the empty sequence (over ${1,2, \ldots, d}$ ). Then for every $k \geq 0, x \in{0,1}^{n}$ and $\sigma_{1}, \sigma_{2}, \ldots, \sigma_{k} \in{1,2, \ldots, d}$, define $F(x, \lambda)=x$ and
$$
F\left(x, \sigma_{1} \sigma_{2} \cdots \sigma_{k}\right)=\sigma_{1}, F\left(g_{\sigma_{1}}(f(x)), \sigma_{2}, \ldots, \sigma_{k}\right)
$$
That is,
$$
\begin{aligned}
F\left(x, \sigma_{1} \sigma_{2} \cdots \sigma_{k}\right) &=\sigma_{1}, \sigma_{2}, \ldots, \sigma_{k}, y \
y &=g_{\sigma_{k}}\left(f\left(\cdots\left(g_{\sigma_{2}}\left(f\left(g_{\sigma_{1}}(f(x))\right)\right)\right) \cdots \cdot\right)\right)
\end{aligned}
$$
where
For every $k: \mathbb{N} \rightarrow \mathbb{N}$, define $F_{k}(\alpha) \stackrel{\text { def }}{=} F\left(x, \sigma_{1}, \ldots, \sigma_{t}\right)$, where $\alpha$ is parsed into $\left(x, \sigma_{1}, \ldots, \sigma_{t}\right)$, so that $t=k(|x|)$ and $\sigma_{i} \in{1,2, \ldots, d}$.
