The parallel repetition conjecture (PRC) of Feige and Lovasz says that the error probability of a two prover one round interactive protocol repeated $n$ times in parallel is exponentially small in $n$. We show that the PRC is true in the case when the bipartite graph of dependence between queries ... more >>>

We study languages with bounded communication complexity in the multiparty "input on the forehead" model with worst-case partition. In the two party case, it is known that such languages are exactly those that are recognized by programs over commutative monoids. This can be used to show that these languages can ... more >>>