4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – AntonioFa
    Commented Jul 11, 2011 at 17:45
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Commented Apr 22, 2013 at 3:57
  • $\begingroup$ @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. $\endgroup$
    – AntonioFa
    Commented Apr 22, 2013 at 15:02
  • $\begingroup$ 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$? $\endgroup$
    – D.W.
    Commented Apr 22, 2013 at 23:29

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.