On compression of non-classically correlated bit strings

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.