I’m happy to unveil a new paper, “A sequence of relaxations constraining hidden variable models”.

Depending on your interests, I’m including two different overviews. One comes from the social networks perspective and the other from the quantum physics perspective. Fundamentally, they are both about detecting hidden variables.

I’ll be giving a plenary talk about this paper at UAI 2011. So if you like hidden variables and you like Barcelona, come see me there!

[Update: Best paper runner-up!]

Quantum perspective

When people like Einstein realized that quantum physics predicts that the outcomes of some experiments are uncertain, he, logically, concluded that the theory is incomplete. There must be some hidden variable that would allow you to predict the outcome perfectly. “God does not play dice.”

On the other hand, Bell’s theorem provides a remarkable retort to this view. Bell showed that there is a limit to how strongly correlated two particles can be if the following assumptions are true:

1) Free will. (We are able to freely choose between two incompatible measurements.)

2) No faster than light signaling. (My choice of measurement on one particle is not instantly transmitted to the other particle.)

3) Hidden variables. (This hidden variable would perfectly predict the outcome of my experiment, regardless of which distant measurements were chosen.)

These assumptions limit how strongly correlated two particles can be. “Entangled” particles in quantum physics go beyond this limit and therefore violate at least one of these assumptions. Einstein called this “spooky action at a distance”.

One amazing thing about Bell’s test is that it made no assumption on what kind of “local hidden variables” were allowed. Despite this, he was able to find a test that conclusively rules them out as an explanation. My paper is, essentially, about how we can easily find tests for hidden variables in other contexts. (The answer: finding the best test can be hard, but we can find good tests using semidefinite relaxations.)

Social networks perspective

You may remember a recent study in the news that said “obesity is contagious“. You may have wondered if it is really possible to show such a thing. Cosma Shalizi wondered the same thing (paper here)and showed that the answer is, generally, no. You can always find an equally good explanation without invoking contagion or influence, that attributes correlations to some hidden variable. For instance, there is some hidden attribute of Alice and Bob that causes them to become friends, and also predisposes them to becoming obese.

How much correlation on a social network can be attributed to these “hidden variable theories”? If these properties are true:

1) No influence

2) Hidden variables (Each person’s actions depend only on their previous actions and the hidden variable.)

3) Stationarity (The hidden variable does not change with time.)

Then we can derive a limit to how correlated two people’s actions can be. Violation of this limit implies either that some influence is involved, or that the hidden variable is changing in time.

Intuitively, imagine I flip a coin and I start calling out the results: “Heads, Heads, Tails, Heads…”. Now, my friend Ditto starts calling out shortly thereafter: “Heads, Heads, Tails, Heads…”. At some point we can be fairly convinced I’m influencing Ditto. The paper just quantifies when we can do this and how confident we can be!