^{n}to Σ

^{n}. Let U represent the uniform distribution on Σ

^{n}and D be the distribution that one gets by applying f to a string drawn from U.

We wish to find f that change x but keep the underlying distribution
close to the same, in particular we want the following properties,

(1) Prob(f(x)≠x)≥2/3 when x is drawn from U.

(2) U and D should be statistically close, informally no algorithm
making a polynomial number of samples will be able to distinguish,
with high confidence, whether those samples came from D or U.

Achieving such an f is easy, consider f that just flips the first bit of x. (1) holds all the time and U=D.

Suppose we add a restriction to f:

(3) In the bits where x and f(x) differ those bits are 1 in x and 0 in
f(x). For example, f(011)=010 is allowed, but f(011)=f(111) is not.

An f fulfilling (1), (2) and (3) is impossible. (1) and (3) means that
f will reduce the number of ones on most of the strings and taking say
n^{3} samples we will notice a statistical difference in the
number of bits which are 1 depending on whether the samples were drawn
from U or D.

Suppose we replaced (3) with a weaker restriction:

(3') In the first bit where x and f(x) differ, that bit is 1 in x an 0
in f(x). So f(110)=011 is allowed but f(001)=010 is not allowed.

Can an f fulfilling (1), (2) and (3') exist? Not so clear, but Peter
Shor found a simple example: f(0^{n})=0^{n}, and for
the other x, f(x)=x-1 where x is viewed as a nonnegative integer
written in binary. D is indistinguishable from U yet f changes nearly
every string.

These questions are related to an old paper I had with Joan Feigenbaum which has gotten some recent attention because of a nice new FOCS paper by Bogdanov and Trevisan that builds on our paper. The proofs in these papers work partly because (1), (2) and (3) cannot all happen even for arbitrary distributions U. Both papers give a negative result for a nonadaptive case; the adaptive case corresponds to (1), (2) and (3') and Shor's example shows that the proof techniques will not directly lead to a solution in the adaptive case which remain open.

## No comments:

## Post a Comment