2
$\begingroup$

Let $f$ be a Boolean function and $\varepsilon > 0$.

There exists a pseudorandom generator $G_f: \{0,1 \}^{n^{\varepsilon}} \to \{0,1 \}^n$ with the following property. Let $T$ be a set and $p(n)$ a polynomial.
If $|\Pr_{r \in \{0,1 \}^n}[r \in T] - \Pr_{r \in \{0,1 \}^{n^{\varepsilon}}}[G_f(x) \in T]| > \frac{1}{p(n)}$ for all large $n$, then there exists a polynomial-size oracle circuit family $\{C_n\}_{n \in \mathbb{N}}$ with oracle $T$ that computes $f$ and queries $T$ non-adaptively.

Roughly speaking, if $T$ exposes generator $G_f$ then there exists a polynomial-size circuit with oracle $T$ that computes $f$.

For simplicity I will consider only oracles $T$ such that $\Pr_{r \in \{0,1 \}^{n^{\varepsilon}}}[G_f(x) \in T] =0$. For oracles $L$ and $T$ having this property we say that $L$ expose $G_f$ not worse than $T$ if $T \subseteq L$.

I want the following generalization of this result. If $T$ exposes generator $G_f$ then there exists a polynomial-size circuit $C$ such that $C^L$ computes $f$ for every oracle $L$ that is not worse than $T$.

Unfortunately, this generator $G$ (based on Nisan-Wigderson generator) does not have this property.

Is it possible to improve $G$ for achieving my goal?

Motivation. In the cited paper ``Power from random strings'' authors consider oracles containing strings with high Kolmogorov complexity, for example oracle $R =\{x | C(x) \ge \frac{x}{2} \}$ where $C$ is some variation of Kolmogorov complexity.

It is natural to consider a spoiled oracle instead of $R$ that answer `yes' if we ask about string $x$ s.t. $C(x) \ge \frac{x}{2} + B$, answer ``no'' if we ask about string $x$ s.t. $C(x) \le \frac{x}{2} - B$ and can answer everything if $\frac{x}{2} - B < C(x) < \frac{x}{2} + B$. Here $B$ is bound for example constant.

If there exists a wishful generator which properties decribed above then some results from ``Power from random strings'' can be generalized for such family of oracles.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.