Combinatorics and quantum nonlocality -: art. no. 047903

We use techniques for lower bounds on communication to derive necessary conditions (in terms of detector efficiency or amount of superluminal communication) for being able to reproduce the quantum correlations occurring in Einstein-Podolsky-Rosen-type experiments with classical local hidden-variable theories. As an application, we consider n parties sharing a Greenberger-Horne-Zeilinger-type state and show that the amount of superluminal classical communication required to reproduce the correlations is at least n(log(2)n-3) bits and the maximum detector efficiency eta(*) for which the resulting correlations can still be reproduced by a local hidden-variable theory is upper bounded by eta(*)less than or equal to8/n and thus decreases with n.