On compression of non-classically correlated bit strings

Abstract

In this short note we present a new approach to non-classical correlations that is based on the compression rates for bit strings generated by Alice and Bob. We use normalised compression distance introduced by Cilibrasi and Vitanyi to derive information-theoretic inequalities that must be obeyed by classically correlated bit strings and that are violated by PR-boxes. We speculate about a violation of our inequalities by quantum mechanical correlations.

This is a substantially revised version of the previous paper. In fact, it is so revised that it is an entirely new paper. All comments are welcome and appreciated