Tight Bounds for Set Disjointness in the Message Passing Model

In a multiparty message-passing model of communication, there are $k$ players. Each player has a private input, and they communicate by sending messages to one another over private channels. While this model has been used extensively in distributed computing and in multiparty computation, lower bounds on communication complexity in this model and related models have been somewhat scarce. In recent work cite{phillips12,woodruff12,woodruff13}, strong lower bounds of the form $Omega(n cdot k)$ were obtained for several functions in the message-passing model; however, a lower bound on the classical Set Disjointness problem remained elusive. In this paper, we prove tight lower bounds of the form $Omega(n cdot k)$ for the Set Disjointness problem in the message passing model. Our bounds are obtained by developing information complexity tools in the message-passing model, and then proving an information complexity lower bound for Set Disjointness. As a corollary, we show a tight lower bound for the task allocation problem cite{DruckerKuhnOshman} via a reduction from Set Disjointness.

Noise vs computational intractability in dynamics

Computation plays a key role in predicting and analyzing natural phenomena. There are two fundamental barriers to our ability to computationally understand the long-term behavior of a dynamical system that describes a natural process. The first one is unaccounted-for errors, which may make the system unpredictable beyond a very limited time horizon. This is especially true for chaotic systems, where a small change in the initial conditions may cause a dramatic shift in the trajectories. The second one is Turing-completeness. By the undecidability of the Halting Problem, the long-term prospects of a system that can simulate a Turing Machine cannot be determined computationally. We investigate the interplay between these two forces -- unaccounted-for errors and Turing-completeness. We show that the introduction of even a small amount of noise into a dynamical system is sufficient to destroy Turing-completeness, and to make the systems long-term behavior computationally predictable. On a more technical level, we deal with long-term statistical properties of dynamical systems, as described by invariant measures. We show that while there are simple dynamical systems for which the invariant measures are non-computable, perturbing such systems makes the invariant measures efficiently computable. Thus, noise that makes the short term behavior of the system harder to predict, may make its long term statistical behavior computationally tractable. We also obtain some insight into the computational complexity of predicting systems affected by random noise.

The Grothendieck constant is strictly smaller than Krivines bound

We prove that $K_G<frac{pi}{2log(1+sqrt{2})}$, where $K_G$ is the Grothendieck constant.