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
40
votes
1answer
605 views

Does Rabin/Yao exist (at least in a form that can be cited)?

In Andrew Chi-Chih Yao's classic 1979 paper he references "M. O. Rabin and A. C. Yao, in preparation". This is for the result that the bounded-error communication complexity of the equality function ...
25
votes
2answers
983 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 ...
22
votes
2answers
1k 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 ...
20
votes
4answers
1k 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, ...
20
votes
2answers
801 views

Deterministic communication complexity vs partition number

Background: Consider the usual two-party model of communication complexity where Alice and Bob are given $n$-bit strings $x$ and $y$ and have to compute some Boolean function $f(x,y)$, where $f:\{0,1\}...
18
votes
2answers
758 views

Bounds on the size of the smallest NFA for L_k-distinct

Consider the language $L_{k-distinct}$ consisting of all $k$-letter strings over $\Sigma$ such that no two letters are equal: $$ L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall i\in[k]...
17
votes
0answers
351 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 ...
15
votes
1answer
431 views

Information complexity of query algorithms?

Information complexity has been a very useful tool in communication complexity, mainly used to lower bound the communication complexity of distributed problems. Is there an analogue of information ...
15
votes
0answers
352 views

Set Intersection lower bounds

Consider $S_1, ...,S_n \subseteq [U]$ where size of $U$ is polylogarithmic in $n$. We allow infinite time to pre-process these sets and then ask queries of the form $S_i \cap S_j$ is empty or not. We ...
15
votes
0answers
349 views

Communication Complexity with real numbers

I'm looking into communication complexity with real numbers. One problem if we want to define this is that one can encode many real numbers $0.a_1a_2a_3... , 0.b_1b_2b_3..., 0.c_1c_2c_3...$ using only ...
14
votes
2answers
875 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$ ...
14
votes
1answer
455 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 ...
13
votes
2answers
441 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 ...
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-...
12
votes
1answer
750 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 ...
12
votes
1answer
522 views

Compressing information about the halting problem for oracle Turing machines

The halting problem is well-known to be uncomputable. However, it is possible to exponentially "compress" information about the halting problem, so that decompressing it is computable. More precisely,...
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
2answers
552 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 ...
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 $\...
11
votes
2answers
472 views

One-way randomized communication complexity of Greater-Than

Let $\mathrm{GT}_n:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ be the greater than function: $\mathrm{GT}_n(x,y)=1$ exactly when the positive integer whose binary representation is $x$ is greater than the ...
11
votes
4answers
249 views

Minimum communication cost for zero knowledge proofs of three colorability

Goldreich et al.'s proof that three colorability has zero knowledge proofs uses bit commitment for an entire coloring of the graph in each round [1]. If a graph has $n$ vertices and $e$ edges, a ...
11
votes
1answer
288 views

Any evidence that Linial, Shraibman lower bound on quantum communication complexity is not tight?

As far as I know, the factorization norm lower bound given by Linial and Shraibman is essentially the only lower bound known for quantum communication complexity (or at least it subsumes all others). ...
11
votes
1answer
462 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 ...
10
votes
1answer
535 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 matrix)...
10
votes
1answer
427 views

Zero error randomized communication complexity vs deterministic communication complexity

It is known that for $\Theta(1)$ error the worst case definition of randomized communication complexity and average case definition are equivalent. But when the error is $0$, the worst case randomized ...
10
votes
1answer
359 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 ...
10
votes
1answer
229 views

Communication problems for which a deterministic direct-sum theorem is not known to hold

It is an old open problem whether a direct-sum theorem holds for deterministic communication complexity, that is, whether solving $t$ independent instances of a problem is $t$ times harder than ...
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 ...
9
votes
1answer
263 views

Regular languages and constant communication complexity

Let $L \subseteq A^*$ be a language, and define $f_L\colon A^* \times A^* \to \{0, 1\}$ by $f_L(x, y) = 1$ iff $x\cdot y \in L$. I'm searching for a reference for: Proposition. $L$ is regular iff ...
8
votes
3answers
790 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 ...
8
votes
1answer
373 views

Lower bound for NFA accepting 3 letter language

Related to a recent question (Bounds on the size of the smallest NFA for L_k-distinct) Noam Nisan asked for a method to give a better lower bound for the size of an NFA than what we get from ...
8
votes
1answer
819 views

Best sources for communication complexity

What are some of the best sources (books and papers) to motivate and learn communication complexity on its own and in connection with its relation to computational complexity theory?
8
votes
2answers
358 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 ...
8
votes
2answers
475 views

Communication complexity problems with linear distance

Are there any known (non-trivial) randomized communication complexity lower bounds for natural gap problems in which the 1-inputs are linearly far from the 0-inputs? That is, partial functions $f:\{0,...
8
votes
2answers
256 views

Communication complexity of approximating the size of set intersection

Consider the set-intersection problem: Alice and Bob each get a subset of $\left\{ 1,\ldots, n\right\}$, and they would like to know whether their sets intersect. This is a canonical problem of ...
8
votes
1answer
270 views

Is there a name for this concept in Communication Complexity?

Let Alice and Bob compute boolean function $f(x_1,\dots,x_{2n})$. Select a random subset $\mathcal I\subseteq\{1,\dots,2n\}$ of cardinality $n$ and let $\mathcal J=\{1,\dots,2n\}\backslash\mathcal I$....
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$, ...
8
votes
3answers
559 views

Communication complexity of finding common element of two subsets

Suppose that Alice receives a subset $S \subseteq \{1,\dots,n\}$ and Bob receives $T \subseteq \{1,\dots,n\}$. It is promised that $\lvert S \cap T \rvert = 1$. What is the randomized communication ...
7
votes
2answers
626 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 ...
7
votes
2answers
191 views

One way communication complexity of multi exact matching

Let Alice have $n$ binary strings, each of length $n$ and let Bob have one binary string of length $n$. Bob has to output $1$ if his string matches any of Alice's exactly and $0$ otherwise. Clearly ...
7
votes
1answer
265 views

A direct-sum theorem for the non-deterministic communication complexity of inequality?

A non-deterministic protocol for the inequality function is a protocol that behaves as follows: Alice and Bob get strings $x,y\in\{0,1\}^n$ respectively, and an untrusted prover is trying to convince ...
7
votes
1answer
886 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 \{1,2,...
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-$...
7
votes
1answer
191 views

Expected vs worst-case communication complexity

In the set disjointness problem of 2-party communication complexity, Alice and Bob are both given an $n$-bit string as input; denoted by $X$ for Alice's input, and $Y$ for Bob's input. They need to ...
7
votes
1answer
177 views

Lower bounds on alternative models of multiparty communication complexity

I'm a newcomer to communication complexity, and so far I've read the chapter in Arora-Barak and some papers giving lower bounds in various applications. A priori the definition of multiparty ...
7
votes
0answers
191 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$ ...
6
votes
2answers
377 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 ...
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 ...
6
votes
1answer
430 views

Nondeterministic communication complexity of set disjointness?

In the two-party setting, bounds of $\Theta(n)$ bits are known for deterministic and bounded-error randomized protocols for $\text{DISJ}_n$. (Here $\text{DISJ}_n$ is the $n$-element set disjointness ...
6
votes
1answer
185 views

0-partition number vs partition number

Denote by $\chi_0(f)$ the minimum number of 0 monochromatic rectangles needed to cover the 0-inputs of $f$, and by $\chi(f)$ the minimum number of monochromatic rectangles needed to cover the all ...