The communication-complexity tag has no wiki summary.
-1
votes
1answer
52 views
Various conjectures which is similar to Log Rank conjecture
Log rank conjecture is one of the most famous open problems in the area of communication compleixty.
Lets consider the two party cdommunication complexity. Alice and Bob have $n$ bit strings $a,b$ , ...
2
votes
0answers
42 views
Are there efficient black-box constructions of sigma-protocols for SAT?
Is there a known black-box construction for the following implication?
non-interactive string commitment that stretches additively by an
amount which does not depend on the string being ...
5
votes
2answers
199 views
Testing for equality with zero error
This question comes from what I asked in a comment here, although I realized that
I don't actually care about which input is less than the other, if they're different.
Alice and Bob have n-bit ...
14
votes
2answers
443 views
Testing for positivity instead of equality
Alice and Bob have n-bit strings, and want to figure out if they're equal while doing little communication. The standard randomized solution is to treat the n-bit strings as polynomials of degree $n$ ...
1
vote
0answers
44 views
mututal data authentication from a short authentication string
For all $n$, $\:$range($\hspace{.005 in}n$)$\:$ is the set of non-negative integers that are less than $n$.
What is known about how many rounds of communication are
needed for mutual data ...
7
votes
1answer
148 views
Why does the log-rank conjecture use rank over the reals?
In communication complexity, the log-rank conjecture states that
$$cc(M) = (\log rk(M))^{O(1)}$$
Where $cc(M)$ is the communication complexity of $M(x,y)$ and $rk(M)$ is the rank of $M$ (as a ...
3
votes
0answers
124 views
Streaming Algorithm Lower Bounds by Communication Complexity
I am learning the methods for proving lower bounds on streaming algorithms using communication complexity.
My question is about a basic technique to prove lower bounds on streaming models using the ...
0
votes
1answer
140 views
“Send Once”-One way Multiparty Communication Complexity
There are plenty results on multiparty communication complexity, and one way protocol which anyone playing communicatin games is able to send one person, is a basic setting.
I want to consider more ...
4
votes
1answer
104 views
Streaming Algorithms: Motivations for estimating frequency moments
The celebrated AMS paper "The space complexity of approximating the frequency moments" defines the problem as following:
Let $a_1, a_2,\dotsc, a_m$ be a sequence of integers where each $a_j \in ...
11
votes
1answer
179 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 ...
7
votes
2answers
140 views
Delegating all of the work to the prover in $\mathcal{MA}$ protocols
An $\mathcal{MA}$ communication complexity protocol is communication complexity protocol that starts with an omniscient prover that sends a proof (that depends on the the specific input of the ...
6
votes
0answers
94 views
Communication complexity of random functions with limited independence
Let $X_0, \ldots, X_{2^n-1}$ be $k$-wise independent random $0/1$ variables over a sample space $\Omega$ and $Prob \left[ X_i = 1 \right] = p$ for every $i$ and some $0 < p < 1$. Let assume $n$ ...
8
votes
1answer
197 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$, ...
3
votes
0answers
124 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
176 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 ...
4
votes
0answers
157 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 ...
0
votes
2answers
255 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
0answers
313 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 ...
9
votes
3answers
198 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
...
8
votes
2answers
447 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 ...
17
votes
0answers
232 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 ...
9
votes
2answers
289 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 ...
7
votes
1answer
76 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 ...
4
votes
1answer
305 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
279 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 ...
9
votes
1answer
216 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 ...
4
votes
1answer
131 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 ...
11
votes
2answers
612 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, ...
8
votes
2answers
313 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 ...
7
votes
3answers
396 views
One way randomised communication complexity of disjointness
I am looking for a reference for the (classical) one way randomised communication complexity of disjointness when the universe can be large. Say Alice and Bob both have sets of size $m$ chosen from a ...
20
votes
2answers
887 views
Protocol partition number and deterministic communication complexity
Besides (deterministic) communication complexity $cc(R)$ of a relation $R$, another basic measure for the amount of communication needed is the protocol partition number $pp(R)$. The relation between ...
15
votes
3answers
566 views
Communication Complexity …Classes?
Discussion:
I've been spending some personal time lately learning various things in communication complexity. For instance, I've re-familiarized myself with the relevant chapter in Arora/Barak, ...
5
votes
1answer
227 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
375 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 ...
6
votes
2answers
297 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 ...
12
votes
2answers
311 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 ...
9
votes
1answer
655 views
Communication complexity for deciding associativity
Let $S=${$0,...,n-1$} and $\circ : S \times S \rightarrow S$. I want to compute the communication complexity of deciding whether $\circ$ is associative.
The model is the following. $\circ$ is given ...
18
votes
1answer
364 views
Approximating the sign rank of a matrix
The sign rank of a matrix A with +1,-1 entries is the least rank (over the reals) of a matrix B which has the same sign pattern as A (i.e., $A_{ij}B_{ij}>0$ for all $i,j$). This notion is important in ...
