Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Changing Strings but not Distributions

Expand Messages
  • Lance Fortnow
    Let f be a function that maps 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
    Message 1 of 1 , Oct 29, 2003
      Let f be a function that maps Σ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 n3 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(0n)=0n, 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 that do not put most of their weight on 0n. 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.

      Posted by Lance Fortnow to My Computational Complexity Web Log at 10/29/2003 09:29:41 AM

      Powered by Blogger Pro

    Your message has been successfully submitted and would be delivered to recipients shortly.