# Questions tagged [communication-complexity]

Questions about the amount of communication required to compute a function whose input is distributed between two or more parties

62 questions
Filter by
Sorted by
Tagged with
1 vote
47 views

### Communication Complexity of "2-Bit"

[For context, I'm trying to work through the derivation of Lemma 2.1 (2-Bit) here, https://users.cs.utah.edu/~jeffp/papers/multiCC-soda12.pdf. ] The '2-Bit' setup is that Alice draws a bit-string of ...
1 vote
41 views

### Why one-sided-error equality problem communication complexity is at least O(n)

I'm trying to solve an exercise from "Algorithmics for hard problems" but I have no idea how to solve it. First the definition of one-sided-error Monte Carlo algorithm is a little different ...
20 views

### When does augmented indexing become easy?

Consider the following problem in 2-party communication complexity, where Alice sends a single message to Bob who must compute the output. Alice gets as input a bit vector $X=(x_1,...,x_N)$, for some ...
• 111
1 vote
55 views

### Nondeterministic Communication Complexity - How to Calculate it from Communication Matrix?

I have been wracking my head around the understanding on how to calculate $N_{1}(f)$ and $N_{0}(f)$ from the communication matrix. Definitions: $N_{1}(f)$ = least cost of non-deterministic protocol ...
• 93
24 views

### How to translate the problem into a Communication Matrix?

Description of the problem: Alice and Bob are both given as input the same graph and vertex $x$ and $y$ respectively. In the graph there are no self-loops and the given vertex can be the same. Prove ...
• 93
1 vote
55 views

### Communication complexity of Dyck language

I've been reading papers on streaming algorithms and ran across the following question which I haven't been able to answer: Consider the Dyck language $Dyck(2)$ over the alphabet $A = \{(,),[,]\}$ and ...
• 11
30 views

### Understanding the proof of a property of universal relation

In the paper Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems, the authors consider the universal relation problem in 2-party communication complexity, which is ...
• 21
1 vote
46 views

### Can a static pre-shared database reduce communication size?

Is the problem of communication with a pre-shared database studied? If yes, what field studies it, or which researchers work on it? Let there be two parties that want to share multiple yet-to-be-...
157 views

### Identify the missing number in a set given its superset

Given a set B and B’s superset A, if B is missing 1 number (let’s y) but don’t know which number it is, how to find that number? That is, B’ = B \ {y}, for some unknown element y B = A \ {x}, for ...
1 vote
73 views

### Communication complexity of index problem with large domains

In the standard definition of the Index problem in one-way 2-party communication complexity, there are two players, Alice and Bob. Alice gets a binary input vector $x$ of length $n$ and Bob gets an ...
84 views

### The universal relation problem in communication complexity

In the universal relation $UR_n$ problem [1] of communication complexity, there are two players Alice and Bob. Alice gets a string $x \in \{0,1\}^n$, Bob gets a string $y \in \{0,1\}^n$ with the ...
1 vote
22 views

### Complexity classes and "local pre-processing"

My question I have two complexity classes, $L$ and $Mod_kL$. I'm confident these classes satisfy $L\subsetneq Mod_kL$, as I'll explain below but you can take for granted for a moment. From these two ...
• 131
1 vote
74 views

### Las Vegas vs Deterministic in one-way communication complexity

I recently learned about the one-way 2-party model of communication complexity in some lecture notes. It seems that all algorithms studied in this model are either deterministic or randomized Monte ...
• 13
33 views

• 11.6k
1 vote
640 views

### Check array in linear time with a constant space complexity

Given an array of integers I have to return true if all the elements in the array are different or all the elements are the same. Otherwise, I have to return false. E.g. ...
• 113
91 views

### Complexity of two-party maximum

Given function $\max\colon \{0, 1\}^{n} \times \{0, 1\}^{n} \rightarrow \{0, 1\}^{n}$ that returns the maximum of two binary $n$-vectors (interpreted as encoding numbers in the range $0,\ldots,2^n-1$),...
288 views

### The Communication Complexity of Majority, What does Bob send to Alice? Can Bob just wait for Alice's input?

I'm following along the examples in https://people.csail.mit.edu/rrw/6.045-2020/note-cc.pdf and in specifically the following text: What’s a good protocol for computing MAJORITY? The natural thing to ...
• 75
187 views

### Does O(1) communication complexity imply that a language is regular?

Let's say that we have a function $g(i,j)$, which is an arbitrary boolean-valued function over $i,j \in \{a,b\}^*$, such that $|i| = |j| = m.$ Moreover, we can also say that $g$ has communication ...
1 vote
100 views

### A communication problem about graphs

An undirected graph on $n$ vertices and $n-1$ edges $G = (V,E)$ is partitioned between two players $A$ and $B$ such that $A$ knows $(V,E_A)$, $B$ knows $(V,E_B)$ and $E_A \dot\cup E_B = E$. Initially, ...
• 151
99 views

### Is unary machine code a concept?

Please assume for the sake of this session that humans can fluently read and understand machine languages and time isn't a problem in that regard. I, not a computer scientist, would at least theorize ...
31 views

### What is the optimal combination of transducers with limited capabilities to a more powerful transducer?

Assume we have a number of transducers with limited information processing capabilities. Are there theoretical results (proofs) on how these transducers can be combined by some sort of communication ...
1 vote
89 views

### Communication Complexity for Product Distributions

In general for the (two-party) set disjointness problem for inputs of length n, we know that the parties need to communicate $\Omega(n)$. Surprisingly, today I discovered (if I understood correctly) ...
• 289
1 vote
104 views

137 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 ...
• 177
285 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 ...
• 2,460
1 vote
125 views

• 1,155