# 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

120 questions
Filter by
Sorted by
Tagged with
73 views

### Communication complexity of edit resilient synchronization

Supposing we have two strings $A$ and $B$ that are both edit distance $\tau$ from each other at two different sites is there a communication complexity model where synchronizing such strings have been ...
125 views

### Lower Bound for Nonzero Terms of a Polynomial Fully Sensitive at 0

Every boolean function $f:\{0,1\}^n\to \{0,1\}$ can be uniquely represented as a multilinear polynomial $p=\sum_{S\subseteq [n]}c_S \chi_s$ where $\chi_s=\prod_{i\in S}x_i$. A boolean function is ...
994 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 ...
475 views

193 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 ...
983 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? ...
112 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 ...
240 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 ...
435 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 ...
182 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 ...
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 ...
173 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 ...
361 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$, ...
64 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 ...
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 ...
153 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 ...
88 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 ...
127 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 ...
361 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 ...
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 ...
758 views

309 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 ...