A little introduction

The Goldreich-Levin Theorem says that

let $f$ a one-way function and set $f'(x,r)=(f(x),r)$ where $|r|=|x|$ then $\langle x, r \rangle = \sum_{i}x_ir_i \mod 2$ is an hard-core predicate of the function $f'$.

With hardcore predicate we mean that if there exists a algorithm $D$ that given $f(x),r$ can predict the value $\langle x, r \rangle$ with probability at least $1/2+\epsilon$ then there exists a inverter algorithm $I$ that with probability $O(\epsilon)$ inverts the fuction $f'$ (using $D$ as subrutine).

From my point of view this is an amazing result in TCS that use simple probabilistic arguments in a really elegant way. Furthermore it's a very good tool for many applications!

For example,the theorem can be rephrased as a coding theory task.

(In the hadamard code we code the message $m \in \{0,1\}^n$ with a codeword $c \in \{0,1\}^{2^n}$ where $c_i= \langle x, \bar{i} \rangle$ and $\bar{i}$ is a binary rappresentation of the number $i$.)

Let $C = Enc(m)\in \{0,1\}^N$ a codeword of hadamard code, we send $C$ over a noise channel and then the receiver obtains $D= C + Error$. If the (normalized) distance between $D$ and $C$ is $1/2-1/p(\log N)$ for some polynomial $p$ then we can reconstruct the message $m$ only by looking few random location of $D$.

In this case $C$ is the binary rappresentation of the function $\langle m,\cdot \rangle$ , $D$ is the binary rappresentation of the predictor.

Goldreich,Rubinfeld and Sudan generalized the theorem: let $\mathbb{F}$ a field such that $|\mathbb{F}|=poly(n)$ and let $f: \mathbb{F}^n\rightarrow\mathbb{F}^m$ a one-way function define $f'(x,r)=(f(x),r)$ as above then $\langle x, r\rangle$ is a hard-core predicate of the fuction $f'$ where now all the operation are over $\mathbb{F}$.

This means that if $D$ is such that $$\Pr[D(f(x),r) = \langle x,r \rangle ] \geq 1/|\mathbb{F}|+p(n)$$ for some polynomial $p$ then we can invert the function $f'$ using $D$.

#My question

Suppose there exists a function $D$ that, given $f(x)$, approximate $\langle x,\cdot \rangle$ with a additive factor $\delta$.

Given a algorithm $D$ such that $\forall r:|D(f(x),r)-\langle x,r \rangle| \leq \delta$ can we construct an Inverter for the function $f'$ from $D$?

A dummy example, suppose there exists $D$ such that, given $f(x)$, it calculates the function $\langle x,\cdot \rangle+1$, obviusly the probability that $D$ predicts $f'$ is 0 but it seem simple to invert the fuction $f'$ given $D$. However in the approximation setting we don't assume that for all input we can know the approximation factor.

A little introduction

The Goldreich-Levin Theorem says that

let $f$ a one-way function and set $f'(x,r)=(f(x),r)$ where $|r|=|x|$ then $\langle x, r \rangle = \sum_{i}x_ir_i \mod 2$ is an hard-core predicate of the function $f'$.

With hardcore predicate we mean that if there exists a algorithm $D$ that given $f(x),r$ can predict the value $\langle x, r \rangle$ with probability at least $1/2+\epsilon$ then there exists a inverter algorithm $I$ that with probability $O(\epsilon)$ inverts the fuction $f'$ (using $D$ as subrutine).

From my point of view this is an amazing result in TCS that use simple probabilistic arguments in a really elegant way. Furthermore it's a very good tool for many applications!

For example,the theorem can be rephrased as a coding theory task.

(In the hadamard code we code the message $m \in \{0,1\}^n$ with a codeword $c \in \{0,1\}^{2^n}$ where $c_i= \langle x, \bar{i} \rangle$ and $\bar{i}$ is a binary rappresentation of the number $i$.)

Let $C = Enc(m)\in \{0,1\}^N$ a codeword of hadamard code, we send $C$ over a noise channel and then the receiver obtains $D= C + Error$. If the (normalized) distance between $D$ and $C$ is $1/2-1/p(\log N)$ for some polynomial $p$ then we can reconstruct the message $m$ only by looking few random location of $D$.

In this case $C$ is the binary rappresentation of the function $\langle m,\cdot \rangle$ , $D$ is the binary rappresentation of the predictor.

Goldreich,Rubinfeld and Sudan generalized the theorem: let $\mathbb{F}$ a field such that $|\mathbb{F}|=poly(n)$ and let $f: \mathbb{F}^n\rightarrow\mathbb{F}^m$ a one-way function define $f'(x,r)=(f(x),r)$ as above then $\langle x, r\rangle$ is a hard-core predicate of the fuction $f'$ where now all the operation are over $\mathbb{F}$.

This means that if $D$ is such that $$\Pr[D(f(x),r) = \langle x,r \rangle ] \geq 1/|\mathbb{F}|+p(n)$$ for some polynomial $p$ then we can invert the function $f'$ using $D$.

My question

Suppose there exists a function $D$ that, given $f(x)$, approximate $\langle x,\cdot \rangle$ with a additive factor $\delta$.

Given a algorithm $D$ such that $\forall r:|D(f(x),r)-\langle x,r \rangle| \leq \delta$ can we construct an Inverter for the function $f'$ from $D$?

A dummy example, suppose there exists $D$ such that, given $f(x)$, it calculates the function $\langle x,\cdot \rangle+1$, obviusly the probability that $D$ predicts $f'$ is 0 but it seem simple to invert the fuction $f'$ given $D$. However in the approximation setting we don't assume that for all input we can know the approximation factor.