Violations of Bell inequalities as lower bounds on the communication cost of non-local correlations

To reproduce in a local hidden variables theory correlations that violate Bell inequalities, communication must occur between the parties. We show that the amount of violation of a Bell inequality imposes a lower bound on the average communication needed to produce these correlations. Moreover, for every probability distribution there exists an optimal inequality for which the degree of violation gives the minimal average communication. As an example, to produce using classical resources the correlations that maximally violate the CHSH inequality, 0.4142 bits of communication are necessary and sufficient. For Bell tests performed on two entangled states of dimension d>=3 where each party has the choice between two measurements, our results suggest that more communication is needed to simulate outcomes obtained from certain non-maximally entangled states than maximally entangled ones.