Questions tagged [communication-complexity]

Questions regarding the amount of communication needed to accomplish a computational task, when the information about the task is spread across several agents

Filter by
Sorted by
Tagged with
8
votes
1answer
271 views

A balanced generalization of Hall’s theorem

Let $X$ and $Y$ be sets, and $\mathcal{B}$ be a partition of $X \times Y$. I would like to prove that there exists a distribution $\mathcal{D}$ over $X \times Y$ whose marginal is uniform over $X$, ...
0
votes
2answers
341 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 ...
11
votes
2answers
553 views

Nonlocal Games and Quantum Communication

I'm currently on the look out for some good reference material relating non-local games with beneficial aspects in quantum communication. For instance, I am aware that non-local games are good at ...
4
votes
0answers
186 views

Do the quantum communication complexity lower bounds hold when parties can send a “duplicated” qubits?

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 ...
3
votes
0answers
154 views

Lower Bound Methods in NonDet Communication Complexity

rank+($M$) is the minimum $r$ such that the following statement holds. The statement : there exists matrices $U,V$ such that $M = UV$ and $U$ has $r$ columns and $V$ has $r$ rows. Is rank+($M$) ...
5
votes
1answer
240 views

Average message complexity for the election problem on graphs

I am currently studying the election problem in distributed algorithms. There, I stumpled over one approach to implement a Chang-Roberts-like message extinction algorithm on graphs without requiring a ...
12
votes
0answers
610 views

Known upper bounds on the communication complexity of Karchmer-Wigderson games

In 1988 Karchmer and Wigderson established a nice characterization of the circuit depth $d$ (DeMorgan circuits) of a Boolean function $f \colon \{0,1\}^n\rightarrow\{0,1\}$: $d$ is exactly the number ...
11
votes
3answers
305 views

Bounds on approximating frequency moments

Let $a_1, a_2,\dotsc, a_m$ be a sequence of integers where each $a_j \in \{1,2,\dotsc,n\}$. For $i \in \{1,2,\dotsc,n\}$, let $m_i = |\{j : a_j = i\}|$. The $k$th frequency moment is defined to be $\...
9
votes
2answers
562 views

Communication complexity with a referee

Assume a framework in communication complexity where we have two players A(lice) and B(ob) and a R(eferee). A and B don't communicate directly with each other. In each round of communication, each of ...
10
votes
1answer
360 views

What is the largest gap between rank and approximate rank?

We know that the log of the rank of a 0-1 matrix is the lower bound of deterministic communication complexity, and the log of the approximate rank is the lower bound of randomized communication ...
18
votes
0answers
353 views

Descriptive complexity of communication complexity classes

It is well known that some major complexity classes, like P or NP, admit a full logical characterization (e.g NP = existential 2nd order logic by Fagin's theorem). On the other hand, one can also ...
7
votes
1answer
94 views

Effect of protocol ordering on multiparty comm. complexity

Brief Background In Multi-Party Protocols by Chandra, Lipton, and Furst [CFL83], a Ramsey-theoretic proof is used to show a lower bound (and later, a matching upper bound) for the predicate Exactly-$...
4
votes
1answer
589 views

Monochromatic Rectangle Tiling

This problem originates from the tiling lowerbound method for communication complexity. In that method, there is a 0-1 matrix $M_{n \times n}$. A rectangle is defined as a submatrix $A \times B$ where ...
6
votes
1answer
617 views

Existence of zero-knowledge proof for location

N items have been placed at specific points on a map. A prize is awarded to the first person who turns in a list with the location of all N items. The location of each item must fall with a distance ...
4
votes
1answer
254 views

Why does deterministic recognition of DYCK(2) languages in the streaming model take linear space?

I was reading the paper "Recognizing Well-Paranthesized Expressions in the Streaming Model" by Magniez, Mathieu and Nayak where they give upper and lower bounds on the space required to recognize DYCK(...
12
votes
2answers
677 views

Best alien communication protocol?

Let's say we discover alien civilizations that are able to send and receive messages using an interstellar digital communications channel. (Say using modulated radio waves, laser pulses, re-...
8
votes
2answers
359 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 ...
6
votes
1answer
360 views

Stronger Lower Bounds on Nondeterministic Multiparty Communication

This is a continuation of my previous question on Lower bounds for Nondeterministic Multiparty Communication. From the answer, the $\mu^\infty$ norm lower bounds nondeterministic multiparty ...
11
votes
1answer
463 views

Lower bounds for Nondeterministic Multiparty Communication

This is a continuation of my previous question on communication lower bounds for partial boolean functions. Can someone suggest any reference on lower bounds for nondeterministic multiparty ...
7
votes
2answers
628 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 ...

1 2
3