All Questions
Tagged with boolean-functions communication-complexity
5 questions
3
votes
0
answers
134
views
Evaluating boolean formula without knowing all values
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 ...
- 31
2
votes
0
answers
79
views
Optimal boolean function encoding with bounded error
Let $F = \{f:\{0,1\}^n \to \{0,1\}\}$ be the set of all boolean functions on $n$ bits. Any such function can be written as a polynomial
$f(x) = a_0 + \sum_i^n a_i x_i + \sum_{i,j}^n a_{i,j} x_i x_j + ...
- 21
2
votes
1
answer
198
views
Real representation versus communication complexity
Suppose that Alice and Bob communicate to compute a function $f:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$. Does the minimal degree of a real polynomial/rational representation of $f$ play a role for ...
- 13.3k
3
votes
1
answer
289
views
Succinct Representation and Communication complexity
Succinct representation is often used to define NEXP or EXP complete problems. For example, when a graph is given as a circuit to compute the existence of edge between vertex $i,j$ for indices of $i,j$...
- 39
7
votes
2
answers
711
views
Communication lower bounds for partial boolean functions
There are well known techniques for proving lower bounds on the communication complexity of boolean functions, like fooling sets, the rank of the communication matrix, and discepancy.
1) How do we ...
- 3,330