Is it possible to compress true random permutation using low order polynomial interpolation? If yes, how it can be achieved?

  • 6
    You can't compress random. If you can it's something more than random. – candied_orange Mar 11 '18 at 1:52
  • 6
    Perhaps if you write more than 2 sentences about this topic someone with the relevant experience can provide more help. What are you trying to achieve? What have you tried? When does this come up? – user1118321 Mar 11 '18 at 3:23
  • 1
  • 1
    @Steve show me how and I'll make you rich. – candied_orange Mar 11 '18 at 14:43
  • 1
    Well having never read it I can tell you how I'd analyze it. Any random can be subjected to any compression technique. If I happen to flip all heads many techniques will be very efficient. If I don't they'll likely all be very poor. If you can find any compression technique that reliably works well on a source of random it means you either got lucky or need a better source of random. – candied_orange Mar 12 '18 at 17:54

This is just an extended comment, too long for a comment. Firstly, the abstract in your link https://link.springer.com/article/10.1007%2FBF02215679 discusses "data compression", but not "random", per se. And as @CandiedOrange first mentioned, random data isn't compressible. And that's simply by definition, e.g., google "Kolmogorov complexity". If you can compress a string, it's not random -- by definition.

But as my comment mentions, permutations aren't entirely random since they're constrained by the requirement that each integer 1,2,...,N appears exactly once. And that means N! possible permutations, versus N^N>>N! possible random sequences.

So here's one possible permutation compression strategy, though it has absolutely nothing to do with interpolation. Choose an enumeration of the permutations of 1...N, whereby you can reconstruct a permutation by its index 1...N! in the enumeration. And that index requires just log_2(N!) bits. In comparison, an enumeration of all sequences would require log_2(N^N) bits to specify an index, whereby random permutations are compressible compared to random sequences.

  • I appreciate you but my professor wants me to use interpolation to compress the data given in the range of 1-N , where each integer appears exactly once. And also I need to recover data by rounding off the result. I don't still understand the concept. coding is not a problem for me. – user9340043 Mar 16 '18 at 16:00
  • @user9340043 Well, yeah, I don't understand the concept, either. You have some function f(x) and a table of its values at some discrete points f(x_i),i=1...n, and some n^th degree polynomial that hits those points, and all that somehow participates in an algorithm to compress random permutations??? When your teacher eventually explains how that works, please edit you question (or post an answer) to explain it to us. – John Forkosh Mar 18 '18 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.