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

learn more… | top users | synonyms

13
votes
0answers
238 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 ...
5
votes
1answer
109 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 ...
4
votes
2answers
205 views

One-way randomized communication complexity of approximate Hamming distance

If Alice and Bob both have $n$ bit strings, consider a one-way randomized communication problem where Bob has to output with some good probability a number which is within a $(1+\epsilon)$ factor of ...
8
votes
1answer
142 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 ...
15
votes
1answer
272 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 ...
4
votes
1answer
114 views

Communication complexity of Independent Set game?

Consider the following communication game. Independent Set game Let $[n] = \{0,1,\dots,n-1\}$ and let $r$ be a positive integer smaller than $n/(1+\log n)$. Alice receives a set $X$ of edges, each ...
1
vote
0answers
49 views

Low rank Log rank conjecture

What is known about log rank conjecture in special situations of $O(\log N)$ rank $0/1$ matrix of size $N\times N$? Is there at least a conditional result showing better than $O(\sqrt{\log N})$ bound? ...
5
votes
2answers
248 views

Research problems in communication complexity

There have been many open challenges questions in this forum. For instance, Research and open challenges in Programming Language Theory What are current open problems in compiler theory? ...
2
votes
0answers
85 views

On a possible probabilistic log-rank conjecture

The communication matrix of a function $f$ is a $2^{n}\times 2^{n}$ matrix $M_f$ where the indices of the rows (columns) correspond to the inputs of Alice (Bob), and each entry $M_f (a,b)$ is the ...
2
votes
1answer
190 views

Is it possible to prove stronger bounds for the deterministic communication complexity compared to nondeterministic communication complexity?

Inspired by the questions Nondeterministic communication complexity of set disjointness?, I was wondering about the following: Is there an example of a function $f$ where the nondeterministic ...
6
votes
1answer
157 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 ...
2
votes
0answers
127 views

$CIS_G$ problem deterministic lower bound

In notes, http://www.cs.toronto.edu/~toni/Courses/CommComplexity2/Lectures/clique-notes.pdf, it is mentioned towards end of section $4$ that http://dl.acm.org/citation.cfm?id=237817 shows that ...
6
votes
1answer
168 views

On the notion of positive rank

The positive rank of a square matrix is defined in Theorem $3$ of "Expressing Combinatorial Optimization Problems by Linear Programs" by Mihalis Yannakakis as follows: given a $n\times n$ matrix $A$, ...
2
votes
1answer
133 views

Real representation versus communication complexity

Suppose that Alice and Bob communicate to compute a function $f:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$. Does the minimal degree of a real polynomial/rational representation of $f$ play a role for ...
4
votes
1answer
164 views

On the notion of positive rank of a matrix

The positive rank of a square matrix is defined in Theorem $3$ of "Expressing Combinatorial Optimization Problems by Linear Programs" by Mihalis Yannakakis as follows: given a $n\times n$ matrix $A$, ...
11
votes
4answers
126 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 ...
2
votes
0answers
39 views

Modern tools deterministic communication applications

Partition number, Fooling-set method along with rank method provide important tools to identify deterministic communication complexity of a function. These techniques were identified some decades ...
30
votes
0answers
323 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 ...
1
vote
1answer
79 views

On connecting combinatorial rectangles

In communication complexity one important object is the combinatorial retangle. Given a $0-1$ square matrix $M$, do their exist permutations $\sigma,\pi$ such that $\sigma M\pi$ consists of only ...
3
votes
1answer
71 views

Classification of a specific problem

Is it known that $\mathsf{IP}\notin\mathsf{NP}^{cc}\cup\mathsf{coNP}^{cc}$ where $\mathsf{IP}$ is inner product communication complexity problem? Where is the classification of $\mathsf{IP}$ currently ...
2
votes
1answer
92 views

Partition Number of a Matrix

Given matrix $M\in\{0,1\}^{n\times n}$, let the minimum number of monochromatic rectangles it can be partitioned be $p$. Let the positive rank of $M$ be $\sigma$ and the rank be $r$. Is it known ...
3
votes
1answer
153 views

The relationship between QCMA and QMA in the Turing and Communication model

First my background about computational complexity is still beginner. Recent paper published by Klauck and Podder [KP14] show that for the first time an exponential gap between computing partial ...
8
votes
1answer
297 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 ...
19
votes
2answers
356 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 ...
9
votes
1answer
384 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?
11
votes
1answer
162 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). ...
7
votes
1answer
152 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 ...
18
votes
2answers
606 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 ...
7
votes
1answer
102 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 ...
8
votes
3answers
269 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 ...
1
vote
1answer
167 views

Succinct Representation and Communication complexity

Succinct representation is often used to define NEXP or EXP complete problems. For example, when a graph is given as a circuit to compute the existence of edge between vertex $i,j$ for indices of ...
0
votes
1answer
154 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
77 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 ...
6
votes
2answers
294 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
588 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$ ...
10
votes
1answer
296 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
227 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 ...
1
vote
1answer
241 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 ...
6
votes
1answer
416 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 ...
14
votes
1answer
284 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
177 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 ...
7
votes
0answers
141 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
236 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
143 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
202 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
174 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
316 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 ...
12
votes
0answers
416 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 ...
10
votes
3answers
241 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
482 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 ...