I am looking for research approaches for the following problem: assume we have a set of $m$ computers, each carries a bit, and a Boolean formula $\varphi$ over those $m$ variables. The computers are not allowed to communicate with each other, only with one "special" computer that can communicate with everyone else. This special computer wants to evaluate $\varphi$ - but with as little communication as possible. For example, if there are 2 computers and $\varphi=x_1 \vee x_2$, - they can agree on the following rule: if their variable is 1, they remain silent, otherwise they send their value to the special computer. In this way, the special computer can evaluate $\varphi$ without knowing all the $m$ values (in some cases).
This problem can be phrased also as follows: what is minimum information required in order to evaluate $\varphi$? in the above example, knowing that one variable equals to 1 is enough to determine the value of the formula. It seems like not so difficult problem, and I was wandering if there are any approaches for this problem (bounds on the minimum information which is needed in the average case for an arbitrary formula, for example). I didn't find much while searching - I'll be glad for direction.

  • 3
    $\begingroup$ This is essentially the simultaneous communication model: people.cs.uchicago.edu/~laci/papers/bgkl-SM.pdf. It has been useful, for example, in analyzing linear sketches in streaming. $\endgroup$ – Sasho Nikolov Oct 1 '16 at 21:57
  • 4
    $\begingroup$ The aspect of being silent doesn't appear in the SM model, but does appear in models described in papers such as "Communication Complexity with Synchronized Clocks" and "Silence is golden and time is money: power-aware communication for sensor networks" $\endgroup$ – Ryan Williams Oct 1 '16 at 22:40
  • $\begingroup$ aren't these just implicants of the function or its negaion? $\endgroup$ – Mikolas Oct 3 '16 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.