Computational Complexity

Wednesday, October 29, 2003

 
Changing Strings but not Distributions

Posted by Lance

Let f be a function that maps Σⁿ to Σⁿ. Let U represent the uniform distribution on Σⁿ 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³ 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ⁿ)=0ⁿ, 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.

9:29 AM # 0 comments

Comment Feeds: This Post All