# Questions tagged [communication-complexity]

The tag has no usage guidance.

36 questions
2answers
63 views

2answers
59 views

0answers
24 views

### Combinatorial model for multiparty communication complexity

Brief introduction: In two-party communication complexity, as presented by Yao in 1979, we model protocols as binary trees whose internal nodes are labeled by either Alice or Bob, and the leaves are ...
0answers
80 views

### Direct sum non-deterministic protocol for the non-equality function

Brief introduction: Let $n \in \mathbb N$. The non-equality function, denoted $NE : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ is defined as follows: \begin{align} \forall x,y\in \{0,1\}^n \;\;\; NE(...
1answer
77 views

1answer
58 views

### About the definition of “differential privacy” in communication complexity

In the context of communication complexity I see a definition of differential privacy which isn't totally clear to me as to why it makes sense. So the two parties $A$ and $B$ draw two strings $X$ ...
1answer
65 views

### How is a communication protocol a mechanism?

Given a finite set $\Sigma$ and a positive integer $n$, a mechanism is a set $\{ \mu_x \vert x \in \Sigma^n \}$ such that $\mu_x$ is a probability measure on some $\sigma-$algebra for each $x$. Now ...
1answer
160 views

1answer
141 views

### The communication complexity of non-equality

I'm familiar with the fooling set technique to obtain lower bounds for communication complexity protocols. The most basic example is the equality function for which the diagonal matrix gives the ...
0answers
88 views

### computational and messages complexity equivalence between STP and Leader election

I'm doing a presentation for a distributed systems and networks course. I'm using the book "Design and Analysis of Distributed Algorithms", written by Nicola Santoro. This book contains the proof of ...
1answer
77 views

### Deterministic Communication Complexity of Equality if inputs differ by at most 1

The set equality problem in 2 party communication complexity is known to require $n$ bits of communication between Alice and Bob, for $n$-bit inputs $X$ and $Y$. Suppose that we promise that the ...
1answer
53 views

### Need help to derive the Complexity!

Please help me regarding this one! What will be the communication and computation complexity of this code?? ...
1answer
62 views

### Understanding the flaw in a proof attempt of the Communication Complexity of Equality

I'm new to communication theory and I've been wondering where the following simple argument fails: Equality Problem We have two players, player 1 Alice who gets an $n$-bit vector $X$ and player 2 Bob ...
1answer
79 views

### Communication complexity of comparing sets, for Bitcoin

In Bitcoin, when one node wants to tell another node about a block, it sends the block header, then all the transactions it contains. This is inefficient, because the receiving node might already have ...
0answers
112 views

### Problems with Θ(n³) complexity on TMs with lower bounds by communication complexity arguments

One of the most used simple examples of application of Communication Complexity is the $\Omega(n^2)$ lower bound for recognizing palindromes of length $2n$ on a single tape Turing machine. Is there ...