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 informa
tion-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.
