Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [communication-complexity]

The tag has no usage guidance.

3
votes
2answers
63 views

Lower bound of disjointness by discrepancy?

I need to show that $Disc_\mu(Disj) \geq \frac{1}{2n+1}$ for any distribution $\mu: \{0,1\}^n \times \{0,1\}^n \to [0,1]$. Disjointness is defined as $Disj(X,Y)=\left\{ \begin{array}[ll]+1 & \...
0
votes
1answer
20 views

Can a transcript change dependent random variables into independent variables?

Let's say $X, Y$ are dependent random variables. Can I find an example such that for a transcript $t$ conditioned on a communication protocol $\Pi=t$, the variables become independent?
0
votes
0answers
33 views

utilization of bitmap protocol

I am curious about utilization calculation in the bitmap protocol. especially if there's a difference between if only station 0 wants to broadcast(and the others doesn't) or only some other station ...
3
votes
2answers
321 views

The Clique vs. Independent Set Problem

Suppose you have an undirected graph $G = (V, E)$, known to both Alice and Bob, Alice gets an independent set of $G$. Bob gets a Clique $B ⊆ V$. Is there any algorithm in $O(\log^2 n)$ bits that ...
0
votes
0answers
15 views

Finding current levels when encoding information in a channel

I am stuck with the following question: In a noised channel with a bandwidth of 4 kHz that has the signal-noise ratio of 30 decibels, if it is known that the maximal broadcasting speed is 16000 bps,...
0
votes
0answers
14 views

Maximal number of parallel cellular calls with no adjacent cells in a hexagonal setting

Is it possible to find an optimization to the following theoretical case? Given is a cellular (phone) system with hexagonal cells, where the volume of transmission and the size of the cells are ...
1
vote
1answer
32 views

Communication complexity: fooling set bound for inner product function

I am trying to prove that the fooling set method does not give a good lower bound for the communication complexity of the inner product function. Specifically, I am trying to show that the best bound ...
1
vote
1answer
57 views

Complexity of sending an $n$-bit string

Consider a $2$-party communication model in which $A$ wish to send to $B$ an $n$-bit string. It is very easy to prove that any deterministic protocol for this problem requires $\Omega(n)$ bits to be ...
1
vote
1answer
27 views

Randomized communication complexity of indexing

The function $\mathrm{INDEX}:\{0,1\}^n\times\{1,\dots,n\}\to \{0,1\}$ is defined as $$\mathrm{INDEX}(x,i)=x_i,$$ where $x=x_1\dots x_n$. I am looking for the randomized communication complexity of $\...
2
votes
2answers
59 views

Lower Bounds for the Set Disjointness Problem

Consider the set disjointness problem. Alice and Bob hold n-bit strings $a$ and $b$ respectively. They would like to compute the function $$ \text{Dis}(a,b) = \begin{cases} 0 &\text{...
3
votes
1answer
34 views

Compute the union of two sets between two endpoints minimizing communication complexity

I have two endpoints, $a$ and $b$, that can communicate through a channel. $a$ is storing a set of fixed-length strings $A = \{a_1, \ldots, a_{N_A}\}$, and $b$ is storing another set of fixed-length ...
1
vote
1answer
49 views

Communication complexity of string matching

let us consider Alice and Bob communicate over channel bit by bit. They have one string over $\{0,1\}^{*}$. Let $x$ (uniformly at random) be the string that Bob have and $y$ be the string that Alice ...
5
votes
1answer
108 views

The communication complexity of Hamming distance mod $4$

If Alice and Bob each have a bit string of length $n$, what is the randomized communication complexity (either one or two-way) of computing the Hamming distance mod $4$? It seems this is hard to ...
2
votes
2answers
108 views

Protocols for “almost equality” with one-sided error

In the well-known communication task EQUALITY, Alice has a string $x$ of $n$ bits, Bob has a string $y$ of $n$ bits, and their task is to determine whether $x = y$. In the public coin model, there is ...
2
votes
1answer
92 views

Theory of message complexity analysis of distributed systems

Inspired by this post, I thought it would be a good idea to ask an analogous question in the context of distributed systems - While most of us are familiar with the notion of Time Complexity as a ...
5
votes
1answer
47 views

Worst known case for log rank conjecture

The log rank conjecture states that there is some universal constant $c > 0$ so that $$CC(f) = O(\log^c \text{rk}\,(M_f))$$ where $f : X \times Y \to \{0, 1\}$ is a boolean function, $CC$ denotes ...
2
votes
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 ...
4
votes
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(...
3
votes
1answer
77 views

Randomized and Deterministic Communication Complexity of a function

I have a problem I'm trying to answer for my homework. The question is: Let $p$ be a prime number and let $GF(p)$ denote the finite field of size $p$. Suppose that A has input $x∈GF(p)$ encoded with $...
-1
votes
1answer
90 views

Communication Complexity and Prefix Codes [closed]

I need an advice. There is in section "V. CONCLUDING REMARKS" of the paper [1], a term that only the autho's paper use: "PREFIX CODING COMMUNICATION". I googled the expression and the only result ...
2
votes
1answer
122 views

Example of reduction in communication complexity

Let us assume the standard situation in communication complexity with two players $P_1,P_2.$ We have a function $f:[n] \times [n] \mapsto \{0,1\}$ that both players known in advance. They wish to ...
1
vote
1answer
74 views

What is a “geometric rectangle”?

In the [Kushilevitz and Nisan 2006, P.10] they give an exercise which says as following: Exercise 1.18: Let $X=Y=\{1,\ldots,n\}$. A geometric rectangle is a set of the form $\{(x,y)|x_{\min} \leq x ...
2
votes
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$ ...
1
vote
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 ...
6
votes
1answer
160 views

A Myhill-Nerode type characterization of the regular languages using fooling sets?

Ultimately, my question is whether it's possible to exactly characterize the regular languages in terms of fooling sets. To help explain my motivation for asking this, here's a quick exposition. Let $...
1
vote
1answer
38 views

Particular function communication complexity computation

Consider a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$. If $f$ satisfies $f(\bar{0})=0$ where $\bar{0}$ is vector of $0$, $f(x)=1$ with every $0/1$ vector of hamming weight $1$, then ...
0
votes
2answers
221 views

Rounds in communication complexity - definition

What does rounds in communication complexity mean in setting of deterministic/non-deterministic $2$ party communication or multi party setting? Is it number of bits exchanged between players ...
5
votes
1answer
61 views

Do correlated inputs imply existence of efficient communication protocols?

Suppose that I have 2 parties Alice and Bob. Alice gets an input $X$ and Bob gets input $Y$ where $X, Y$ are $n$-bit strings. In the classic communication complexity world, computing a function such ...
1
vote
0answers
29 views

What's the name of this multiparty problem?

Suppose I have $k$ players $P_1,\dots,P_k$ that can communicate with each other directly by sending messages. For defining the inputs, we consider a fixed set of names $N$ which are integers in $[1,...
3
votes
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 ...
1
vote
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 ...
1
vote
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 ...
0
votes
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?? ...
3
votes
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 ...
4
votes
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 ...
6
votes
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 ...