<p>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).<br>
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. </p>

CC BY-SA 3.0
2016-10-01T21:57:03.893Z
This is essentially the simultaneous communication model: http://people.cs.uchicago.edu/~laci/papers/bgkl-SM.pdf. It has been useful, for example, in analyzing linear sketches in streaming.
Sasho Nikolov
CC BY-SA 3.0
2016-10-01T22:40:32.173Z
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"
Ryan Williams
CC BY-SA 3.0
2016-10-03T13:12:09.923Z
aren't these just implicants of the function or its negaion?
Mikolas
<lo.logic><boolean-functions><communication-complexity><boolean-formulas>
Evaluating boolean formula without knowing all values
John.C
# Evaluating boolean formula without knowing all values

(Asked by: username_0 on 2016-10-01)

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.

**Tags:** lo.logic, boolean-functions, communication-complexity, boolean-formulas

> **Comments:**
> **username_1**: This is essentially the simultaneous communication model: http://people.cs.uchicago.edu/~laci/papers/bgkl-SM.pdf. It has been useful, for example, in analyzing linear sketches in streaming.  
> **username_2**: 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"  
> **username_3**: aren't these just implicants of the function or its negaion?  

---

## 0 answers

