# Beating Nonuniformity by Oracle Access

Informally, we say that a Turing machine $M(\cdot)$ approximates a function $f(\cdot)$ if their outputs on a series of inputs are indistinguishable.

More formally, let $L$ be a language, $M(\cdot)$ be a probabilistic polynomial-time (PPT) Turing machine, and $f(\cdot)$ be a polynomially bounded function: $f \colon \{0,1\}^n \to \{0,1\}^{\text{poly}(n)}$. We say that $M$ approximates $f$ on $L$ if for all families of polynomial-size binary circuits $D = \{D_k\}$, and for all large enough $x \in L$, it holds that the following quantity:

$|\Pr[D_n(M(x))=1] - \Pr[D_n(f(x))=1]|$

is negligible, i.e. a positive quantity smaller than the reciprocal of any positive polynomial (For instance, $2^{-n}$ and $n^{-\log n}$ are negligible, but $1 \over 2$ and $n^{-2}$ are not.) Here, $n=|x|$.

Since $D_n$ receives an advice, there are tests which $D_n$ can perform but $M(x)$ cannot.

This question seeks the existence of functions which are not approximable in the above sense, but are approximable if $M$ has black-box or code access to $D$.

The formalization follows:

Assume the following:

1. $L$ is a decidable language;
2. $f$ is a polynomially bounded function;
3. $M$ is an oracle PPT Turing machine;
4. $D = \{D_k\}$ is a family of polynomial-size binary circuits.
5. $x \in L$

$L$, $f$, $M$, $D$, and $x$ are selected in the given order; so, for example, $D$ may depend on $M$ but not vice versa. Let $n$ denote the size of $x$.

If $M$ is not explicitly equipped with an oracle, we implicitly assume that there's an oracle which for all queries, returns a special $\perp$ symbol. (Meaning that "I don't know the answer to your query.")

The question is,

Does there exist a decidable language $L$, and a poly-bounded function $f$, such that any PPT machine $M'$ fails to approximate $f$ on infinitely many $x\in L$, but there exists some PPT oracle machine $M$ such that for all poly-size circuit $D$, machine $M^{D_n}$ can approximate $f$ on $L$. That is, the following quantity is negligible:

$|\Pr[D_n(M^{D_n}(x))=1] - \Pr[D_n(f(x))=1]|$

Moreover:

What if $M$ was given an encoding of $D_n$ instead of oracle access to it? That is, what if we required that $M(\langle D_n \rangle, \cdot)$ should approximate $f(\cdot)$ on $L$? (here, $\langle D_n \rangle$ denotes the encoding of $D_n$ in some canonical way.) This means that the following quantity is negligible:

$|\Pr[D_n(M(\langle D_n \rangle, x)=1] - \Pr[D_n(f(x))=1]|$

• Well, the title is so bad. Suggestions are welcome. – M.S. Dousti Feb 8 '11 at 10:56
• I'm a little confused. What are the semantics of "$S(x)$" and "$S(x,\langle D_n \rangle)$", when $S$ is a PPT machine with an oracle? What do you want the oracle queries to return when there is no oracle to query? – Ryan Williams Feb 8 '11 at 11:39
• @Kaveh: I tried hard but didn't get what you mean. Could you please elaborate? @Ryan: You're right. One may assume that in such cases, $S$ is equipped with an oracle which for all queries, returns a special "NULL" symbol. Moreover, observe that for the second part of the question, S need not be a query machine. (When comparing $S(x)$ and $S(x,\langle D_n \rangle)$.) – M.S. Dousti Feb 8 '11 at 12:14
• Is D acting like a "Distinguisher"? What do you mean by assuming oracle access to the same machine that is going to distinguish it? Can you provide me with the idea where this question is risen? BTW, sorry to ask this preliminary question but is noticeable defined to be 1-negligible, in that case how $n^{-2}$ can be noticeable? – Yasser Sobhdel Feb 8 '11 at 12:36
• Can D depend on x? If so, I do not know what it means for D to be polynomial size. If not, it seems to me that your definition of approximability is really about approximating the probability distribution generated by applying f to the uniform bit string, not approximating the function f. – Tsuyoshi Ito Feb 9 '11 at 23:43