We introduce a generalization of the standard framework for studying the difficulty of two-prover games. Specifically, we study the model where Alice and Bob are allowed to communicate (with information constraints) --- in contrast to the usual two-prover game where they are not allowed to communicate after receiving their respective ... more >>>

Agreement tests are a generalization of low degree tests that capture a local-to-global phenomenon, which forms the combinatorial backbone of most PCP constructions. In an agreement test, a function is given by an ensemble of local restrictions. The agreement test checks that the restrictions agree when they overlap, and the ... more >>>

Nisan and Szegedy showed that low degree Boolean functions are juntas. Kindler and Safra showed that low degree functions which are *almost* Boolean are close to juntas. Their result holds with respect to $\mu_p$ for every *constant* $p$. When $p$ is allowed to be very small, new phenomena emerge. ... more >>>