We prove that an \omega(log^3 n) lower bound for the three-party number-on-the-forehead (NOF) communication complexity of the set-disjointness function implies an n^\omega(1) size lower bound for tree-like Lovasz-Schrijver systems that refute unsatisfiable CNFs. More generally, we prove that an n^\Omega(1) lower bound for the (k+1)-party NOF communication complexity of set-disjointness ... more >>>

Games may be represented in many different ways, and different representations of games affect the complexity of problems associated with games, such as finding a Nash equilibrium. The traditional method of representing a game is to explicitly list all the payoffs, but this incurs an exponential blowup as the number ... more >>>

We study the computational complexity of counting the fixed point configurations in certain discrete dynamical systems. We prove that both exact and approximate counting in Sequential and Synchronous Dynamical Systems (SDSs and SyDS, respectrively) is computationally intractable, even when each node is required to update according to a symmetric Boolean ... more >>>