# A approximation version of the Goldreich-Levin Theorem

## 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.

• Okay, if $\delta$ is a $poly(n)$ then given $D$ that approximate $f$ the predictor $D'(f(x),r)=D(f(x),r)+ y$ where $y$ is uniformly random in $\{-\delta,..,\delta\}$ fits the standard hypothesis. but can we do better? – AntonioFa Jul 11 '11 at 17:45
• The condition $|D(f(x),r)-\langle x,r\rangle| \le \delta$ seems odd. It is too strong: the only way to satisfy this is if $D(f(x),r)=\langle x,r\rangle$ for all $x,r$ (assuming you intend $\delta < 1/2$). What condition did you actually intend? Did you intend it to be some probabilistic statement, akin to that found in the Goldreich-Levin Theorem? – D.W. Apr 22 '13 at 3:57
• @D.W. $\delta$ is greater than 1. Here i'm looking for a learner of $x$ given access to a function that outputs an approximation of $<x,y>$, obviusly the space $\mathbb{F}$'s cardinality is bigger than 2. – AntonioFa Apr 22 '13 at 15:02
• Ahh, I see. So you might want to edit the question to clarify that $f$ is a function over the field $\mathbb{F}$ (e.g., $f:\mathbb{F}^n \to \mathbb{F}^m$) and something similar for $D$. Anyway: Do you have a link to the Goldreich, Rubinfeld, and Sudan paper that proves the more general theorem? Also, do you have a particular value of $\delta$ that you care about, or are you interested in any result at all where $\delta \ge 1$? – D.W. Apr 22 '13 at 23:29