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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.