<h2>A little introduction</h2>
<p>The <strong>Goldreich-Levin Theorem</strong> says that</p>
<blockquote>
<p>let <span class="math-container">$f$</span> a one-way function and set <span class="math-container">$f'(x,r)=(f(x),r)$</span> where <span class="math-container">$|r|=|x|$</span> then <span class="math-container">$\langle x, r \rangle = \sum_{i}x_ir_i \mod 2$</span> is an hard-core predicate of the function <span class="math-container">$f'$</span>.</p>
</blockquote>
<p>With <strong>hardcore predicate</strong> we mean that if there exists a algorithm <span class="math-container">$D$</span> that given <span class="math-container">$f(x),r$</span> can predict the value <span class="math-container">$\langle x, r \rangle$</span> with probability at least <span class="math-container">$1/2+\epsilon$</span> then there exists a inverter algorithm <span class="math-container">$I$</span> that with probability <span class="math-container">$O(\epsilon)$</span> inverts the fuction <span class="math-container">$f'$</span> (using <span class="math-container">$D$</span> as subrutine).</p>
<p>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!</p>
<p>For example,the theorem can be rephrased as a coding theory task.</p>
<p>(In the hadamard code we code the message <span class="math-container">$m \in \{0,1\}^n$</span> with a codeword <span class="math-container">$c \in \{0,1\}^{2^n}$</span> where <span class="math-container">$c_i= \langle x, \bar{i} \rangle$</span> and <span class="math-container">$\bar{i}$</span> is a binary rappresentation of the number <span class="math-container">$i$</span>.)</p>
<p>Let <span class="math-container">$C = Enc(m)\in \{0,1\}^N$</span> a codeword of hadamard code, we send <span class="math-container">$C$</span> over a noise channel and then the receiver obtains <span class="math-container">$D= C + Error$</span>. If the (normalized) distance between <span class="math-container">$D$</span> and <span class="math-container">$C$</span> is <span class="math-container">$1/2-1/p(\log N)$</span> for some polynomial <span class="math-container">$p$</span> then we can reconstruct the message <span class="math-container">$m$</span> only by looking few random location of <span class="math-container">$D$</span>.</p>
<p>In this case <span class="math-container">$C$</span> is the binary rappresentation of the function <span class="math-container">$\langle m,\cdot \rangle$</span> , <span class="math-container">$D$</span> is the binary rappresentation of the predictor.</p>
<p>Goldreich,Rubinfeld and Sudan generalized the theorem: let <span class="math-container">$\mathbb{F}$</span> a field such that <span class="math-container">$|\mathbb{F}|=poly(n)$</span> and let <span class="math-container">$f: \mathbb{F}^n\rightarrow\mathbb{F}^m$</span> a one-way function define <span class="math-container">$f'(x,r)=(f(x),r)$</span> as above then <span class="math-container">$\langle x, r\rangle$</span> is a hard-core predicate of the fuction <span class="math-container">$f'$</span> where now all the operation are over <span class="math-container">$\mathbb{F}$</span>.</p>
<p>This means that if <span class="math-container">$D$</span> is such that <span class="math-container">$$\Pr[D(f(x),r) = \langle x,r \rangle ] \geq 1/|\mathbb{F}|+p(n)$$</span> for some polynomial <span class="math-container">$p$</span> then we can invert the function <span class="math-container">$f'$</span> using <span class="math-container">$D$</span>.</p>
<h1>My question</h1>
<p>Suppose there exists a function <span class="math-container">$D$</span> that, given <span class="math-container">$f(x)$</span>, approximate <span class="math-container">$\langle x,\cdot \rangle$</span> with a additive factor <span class="math-container">$\delta$</span>.</p>
<blockquote>
<p>Given a algorithm <span class="math-container">$D$</span> such that <span class="math-container">$\forall r:|D(f(x),r)-\langle x,r \rangle| \leq \delta$</span> can we construct an Inverter for the function <span class="math-container">$f'$</span> from <span class="math-container">$D$</span>?</p>
</blockquote>
<p>A dummy example, suppose there exists <span class="math-container">$D$</span> such that, given <span class="math-container">$f(x)$</span>, it calculates the function <span class="math-container">$\langle x,\cdot \rangle+1$</span>, obviusly the probability that <span class="math-container">$D$</span> predicts <span class="math-container">$f'$</span> is 0 but it seem simple to invert the fuction <span class="math-container">$f'$</span> given <span class="math-container">$D$</span>. However in the approximation setting we don't assume that for all input we can know the approximation factor.</p>

CC BY-SA 3.0
2011-07-11T17:45:32.157Z
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
CC BY-SA 3.0
2013-04-22T03:57:13.463Z
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.
CC BY-SA 3.0
2013-04-22T15:02:25.853Z
@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
CC BY-SA 3.0
2013-04-22T23:29:43.463Z
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.
<cc.complexity-theory><cr.crypto-security><approximation-algorithms><one-way-function>
A approximation version of the Goldreich-Levin Theorem
AntonioFa
# A approximation version of the Goldreich-Levin Theorem

(Asked by: username_0 on 2011-07-11)

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

**Tags:** cc.complexity-theory, cr.crypto-security, approximation-algorithms, one-way-function
> **Comments:**
> **username_0**: 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?  
> **username_1**: 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?  
> **username_0**: @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.  
> **username_1**: 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$?  

---

## 0 answers

