Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with communication-complexity
Search options not deleted
user 317
Questions regarding the amount of communication needed to accomplish a computational task, when the information about the task is spread across several agents
14
votes
1
answer
492
views
Best communication complexity lower bound of disjointness
It is well known that no deterministic two-party protocol can solve disjointness problem (DISJ) on $n$-bit inputs without sending $n+1$ bits in the worst case (see, e.g., the book by Kushilevitz and N …
- 795
14
votes
2
answers
475
views
multi-party Communication complexity of "Set Partition problem"
In an application I'm considering, I need to know the communication complexity of the following problem:
Given $n$, let $S$ be the set of integers from $1$ to $n$. Alice, Bob, and Carol each receive …
- 795
2
votes
1
answer
95
views
Communication complexity of graph isomorphism with 2-sided error
Update: After some clarification, the final clarified version turns out to be too simple (see the accepted answer). I'm still interested in the multigraph and promised version mentioned in the comment …
- 795
1
vote
2
answers
369
views
Are Alice and Bob allowed to copy qubits in quantum communication complexity model?
In quantum communication complexity, we always assume that Alice and Bob have unlimited computational power and are still prove lower bounds such as the $\Omega(n)$ lower bounds of parity.
What happ …
- 795
5
votes
0
answers
196
views
Do the quantum communication complexity lower bounds hold when parties can send a "duplicate...
This question continues from the previous question where I mistakenly asked a question that is too general.
In quantum communication complexity, we always assume that Alice and Bob have unlimited co …
- 795
8
votes
2
answers
380
views
Finding out a set by intersection comparison
The following problem recently emerged from my research and I would like to ask if anyone knows if this problem was considered before or has heard of anything that might be related.
The general sett …
- 795