Notation:

${0, 1}^{L}$ and ${0, 1}^{*}$ are the sets of all bitstrings of length $L,$ and the set of all finite bitstrings, respectively. Elements of these sets are denoted by $x$ . The length $i$ prefix of $x$ is denoted by $x_{: i}$ .

$B_{L}$ is the set of all satisfiable booleans with all variables having an index $\leq L$ , and $B$ is the set of all satisfiable booleans. Similarly, $B_{* L}$ and $B_{*}$ are the set of all booleans with all variables having an index $\leq L$ , and the set of all booleans. Elements of these sets are denoted by $B$ . $B \land B^{'}$ is also a boolean. Bitstrings $x$ may be interpreted as boolean constraints saying that the prefix of the bitstring must equal $x$ .

$f$ is a function $N^{+} \to N^{+}$ that is time-constructible, monotonically increasing, and $f (t) > t$ , which gives the runtime bound for traders.

$l$ is some function $N^{+} \to N^{+}$ upper-bounded by $2^{f (t)}$ that is time-constructible, monotonically increasing, and $l (t) > t$ . It gives the most distant bit the oracle inductor thins about on turn $t$ .

$d$ is the function $N^{+} \to N^{+}$ given by $d (t) = l (t) + ⌈ {log}_{2} l (t) ⌉ + 2 t + 7$ , giving the number of iterations of binary-search deployed on turn $t$ .

$δ$ is the function $N^{+} \to [0, 1] \cup Q$ given by $δ (t) = 2^{- (t + 3)}$ . It gives the proportion of the inductor distribution that is made up by the uniform distribution.

The operations $query(A,p)$ and $flip(p)$ take unit time to execute in our model of computation, though the input still has to be written down in the usual amount of time.

Given some arbitrary distribution $Δ$ over ${0, 1}^{L}$ , and a $B \in B_{* L}$ , $Δ (B)$ is the probability mass assigned to bitstrings that fulfill $B$ . Given a $B \in B_{L}$ , $Δ_{B}$ is the conditional distribution given by $Δ_{B} (x) = \frac{Δ (B \land x)}{Δ (B)}$ . $Δ_{B}^{*}$ is the distribution induced by $Approx(Δ,L,D,B)$ . There is an implicit dependence on $D$ which will be suppressed in the notation.

Lemma 1 (n-Lemma): Let $ϵ = 2^{- D}$ . Given some distribution $Δ$ over ${0, 1}^{L}$ for which $\forall x \in {0, 1}^{L} : Δ (x) \geq n ϵ$ , then

$\forall B \in B_{L}, x \in {0, 1}^{L} : {(\frac{n - 1}{n + 1})}^{L} Δ_{B} (x) \leq Δ_{B}^{*} (x) \leq {(\frac{n + 1}{n - 1})}^{L} Δ_{B} (x)$ .

To begin with, if $x$ is incompatible with $B$ , $Δ_{B}^{*} (x) = 0$ by the construction of $Approx$ , and the inequality is trivial. So we can consider the case where $x$ is compatible with $B$ . Given $σ$ as a strict prefix of $x$ , abbreviate $NextBit(Δ,L,D, | σ | + 1,B, σ)$ as $N B (σ)$ .

Because we're using a binary-search depth of $D$ on each bit, and taking the average of the interval, the probabilities are approximated to within $\frac{ϵ}{2}$ .

$\frac{Δ (B \land σ 1) - ϵ}{Δ (B \land σ) + ϵ} < \frac{Δ (B \land σ 1) - \frac{ϵ}{2}}{Δ (B \land σ) + \frac{ϵ}{2}} \leq P (N B (σ) = 1) \leq \frac{Δ (B \land σ 1) + \frac{ϵ}{2}}{Δ (B \land σ) - \frac{ϵ}{2}} < \frac{Δ (B \land σ 1) + ϵ}{Δ (B \land σ) - ϵ}$

Tak...

3

Oracle Induction Proofs

3