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
2 votes
1 answer
135 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 ...
Turbo's user avatar
  • 12.9k
2 votes
1 answer
181 views

Why not include private randomness in internal communication information definition?

I am using https://www.cs.toronto.edu/~toni/Courses/CommComplexity2014/Lectures/lecture12.pdf as a reference. This isn't exactly a research question but I can't find a good place to ask it. Suppose ...
user135743's user avatar
2 votes
1 answer
323 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 ...
poul juan's user avatar
2 votes
1 answer
146 views

Nondeterministic communication complexity

Let $X$ and $Y$ be finite sets and $f : X \times Y \to \{0,1\}$. I am confused about the definition of the deterministic communication complexity of $f$, denoted $N^1(f)$, or rather about the ...
user101010's user avatar
2 votes
1 answer
195 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 ...
Turbo's user avatar
  • 12.9k
2 votes
0 answers
93 views

Subtle part of seeing $C(F) \geq \chi(f)$

This question is certainly below research level, however I figured I would get the best answer here. I just started learning about computational complexity (from Arora and Barak) and I have a ...
user101010's user avatar
2 votes
0 answers
102 views

Lower bounds for list/set data structures without delete

I'm interested in lower bounds on the amortized time cost for either of the following dynamic data structure problems, in the cell probe or RAM model, or any model that lets us do operations on words ...
Dustin Wehr's user avatar
2 votes
0 answers
130 views

What is the communication complexity of approximating addition?

In my circuit complexity research, I came across the need to find the communication complexity of approximating addition. Specifically, the class of problems I am interested in is parametrized by four ...
exfret's user avatar
  • 643
2 votes
0 answers
79 views

Optimal boolean function encoding with bounded error

Let $F = \{f:\{0,1\}^n \to \{0,1\}\}$ be the set of all boolean functions on $n$ bits. Any such function can be written as a polynomial $f(x) = a_0 + \sum_i^n a_i x_i + \sum_{i,j}^n a_{i,j} x_i x_j + ...
philippe's user avatar
2 votes
0 answers
84 views

Number of $0/1$-monochromatic rectangles and communication complexity

What is the relation between number $0$-monochromatic rectangles in characteristic matrix and communication complexity? What is the relation between number $1$-monochromatic rectangles in ...
Turbo's user avatar
  • 12.9k
2 votes
0 answers
115 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 ...
Turbo's user avatar
  • 12.9k
2 votes
0 answers
67 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 ...
Turbo's user avatar
  • 12.9k
2 votes
0 answers
203 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 ...
user avatar
1 vote
2 answers
363 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 ...
Danu's user avatar
  • 763
1 vote
1 answer
118 views

Communication complexity of reconstructing a random bit-string of length $n$

This seems like a folklore claim but I cannot find any reference to it. If Alice has a bit-string of length $n$ where each entry is independently set to 0 or 1 equiprobably, and Bob's goal is to ...
polar_bear_cheese's user avatar
1 vote
1 answer
123 views

Using a probability distribution in the fooling set technique for communication complexity

I'm reading through the communication complexity book of Kushilevitz and Nisan, and in the section about fooling sets I encountered this proposition: Let $\mu$ be a probability distribution of $X\...
NNN's user avatar
  • 123
1 vote
1 answer
174 views

Average-case randomized communication complexity in the small-advantage regime

Let $f\colon \{0, 1\}^n \times \{0, 1\}^n \to \{0, 1\}$. I'm interested in randomized communication protocols $\pi$ that compute $f$ in the weak sense that $$ \Pr_{x, y}\left[\Pr_r[\pi(x, y, r) = f(x, ...
William Hoza's user avatar
  • 1,733
1 vote
1 answer
120 views

Communication complexity of equality on graphs

I came upon a nice observation in communication complexity, and I was wondering if it was already known. Consider the following variant of the equality problem: There is a fixed graph $G$ that is ...
Or Meir's user avatar
  • 5,460
1 vote
1 answer
102 views

Composition theorem for randomized communication complexity

I am currently organizing the literature of composition theorem, and I found the paper by https://www.research.cs.rutgers.edu/~troyjlee/Composition.pdf, in their theorem 5, I find $$ R_{1/4} (f \circ ...
exteral's user avatar
  • 113
1 vote
1 answer
82 views

Matrix rank approximation

I am aware of the problem of low rank approximation of matrices which has been studied in various models of computation. My question is the following: What is the status of approximating rank of a ...
withhighprob's user avatar
1 vote
0 answers
18 views

How to calculate the data transmission rate with path-loss?

We aim to calculate the data transmission rate when sending results from the server back to the user's device. Using the notation: ( B_v ): wireless bandwidth of the server ( P_v ): server's ...
user4594525's user avatar
1 vote
0 answers
66 views

How to formulate the log-rank conjecture for non-boolean functions?

The log-rank conjecture states that there is a constant $C$ such that for every two-party Boolean function $f$ it holds: $D(f) = O((\log \text{rank} (f))^C)$. If $f$ is not a boolean function then ...
Alexey Milovanov's user avatar
1 vote
0 answers
75 views

communication complexity lower bound for identifying coordinate in which two strings differ

This is a question from Rao and Yehudayoff's "Communication Complexity and Applications" textbook that I've been thinking about for a while. Suppose Alice has a string $x\in\{0,1\}^n$ that ...
Ash's user avatar
  • 49
1 vote
0 answers
50 views

What is known about simultaneous protocol set disjointness?

Assume that Alice and Bob have sets $A,B\subseteq[n]$ of size $|A|=|B|=k$. In the simultaneous protocol, they both send a message to Carol (that doesn't observe $A$ and $B$) which needs to determine ...
John's user avatar
  • 11
1 vote
0 answers
46 views

Quantum Communication Complexity Bound on Vector Inner Product

Say Alice has a (complex) vector $a\in\mathbb{C}^d$, and interacts with Bob in a quantum communication protocol (sending qubits back and forth). At the end of the protocol, Bob produces a guess $b\in\...
Yang's user avatar
  • 11
1 vote
0 answers
74 views

Algorithmic game theory with decentralized mechanism of exchanging information

An interesting topic that I want to understand has to do with the decentralized exchange of information among a network of agents, however there is not a specific theory to make such a mathematical ...
Nav89's user avatar
  • 209
1 vote
0 answers
127 views

Deterministic one way communication complexity for message with arbitrary length

Let Alice have a binary string of length $n$ that it wants to send to Bob along a one-bit communication channel. However, Bob does not know the length of the message. I have been looking into ...
Koko Nanahji's user avatar
1 vote
0 answers
430 views

communication complexity lower bound for computing median

In the textbook by Kushilevitz/Nisan, they give an $O(\log n)$-bit protocol for computing the median in the standard 2-party model of communication complexity, where Alice is given a set $X \subseteq [...
JohnDoe's user avatar
  • 11
1 vote
0 answers
407 views

Minimum number of hours of speech needed to train a neural net to recognize speech [closed]

From a theoretical computer science point of view, is there a lower limit on the number of hours of speech needed to train a neural net to translate speech to text? An estimate from CMU is 3000-5000 ...
Lars Ericson's user avatar
1 vote
0 answers
77 views

Bipartite formula complexity lower bound

I'm trying to understand the paper The Bipartite Formula Complexity of Inner Product is Quadratic, by Avishay Tal. The argument is recapped here. I am having trouble understanding the proof Theorem 3 ...
NNN's user avatar
  • 123
1 vote
0 answers
96 views

How does Best Partition Communication Complexity behave under input transformations?

I'm looking for references about the behavior of communication complexity under input transformations. A specific toy example of the kind of question I'm interested in is the following. Let $f(x_1,......
verifying's user avatar
  • 1,072
1 vote
0 answers
51 views

What is the best known gap between ZPP and Deterministic communication complexity? [duplicate]

I know that $N(f) \times coN(f) \geq D(f)$. This means that $ZPP(f) \geq \sqrt{D(f)}$. Is this separation tight?
ivmihajlin's user avatar
1 vote
0 answers
157 views

On the log rank conjecture

We think the log rank conjecture is true over $\{0,1\}$ real matrices and over any fixed alphabet matrix. What is the fastest function $f(r)$ of rank $r$ such that the log rank conjecture over $\{0,1\...
Turbo's user avatar
  • 12.9k
1 vote
0 answers
156 views

Distribution attaining minimum discrepancy of disjointness function

Is it true that for the optimal distribution $\nu$ (not necessarily uniform) that attains minimum discrepancy $\mathsf{disc}(\mathsf{DISJ}_n)$ for the disjointness function $\mathsf{DISJ}_n$ we have ...
Turbo's user avatar
  • 12.9k
0 votes
1 answer
69 views

Deterministic communication complexity of refinement

A partition of $[n]$ is a collection $\mathcal{P}$ of non-empty subsets of $[n]$ such that for each $i \in [n]$ there is a unique $P \in \mathcal{P}$ with $i \in P$. For partitions $\mathcal{P}, \...
user1868607's user avatar
  • 1,017
0 votes
1 answer
265 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$ , ...
echuly's user avatar
  • 549
0 votes
1 answer
69 views

Communication complexity of correctly recovering 99% of a random bit string

Suppose Alice has a bit string of length $n$ where $n/2$ bits are chosen uniformly at random to be 1's; and the rest are 0's. Alice sends a message to Bob. If Bob needs to reconstruct the bit string, ...
polar_bear_cheese's user avatar
0 votes
1 answer
144 views

String distance communication complexity

Consider $(\alpha,t)$-String distance where Alice has $x\in\{0,1\}^n$ and Bob has $y\in\{0,1\}^n$ and they have to decide if $(1-\alpha)t\leq|x\oplus y|\leq (1+\alpha)t$ or not when $\alpha\in[0,1)$ ...
Turbo's user avatar
  • 12.9k
0 votes
0 answers
71 views

Jukna Boolean Function Complexity Exercises 7.2 & 7.3

The two exercises go like following: 7.2. Show that $STCON_n$ can be computed by a monotone nondeterministic branching program of size $\mathcal{O}(n^2)$. Hint: Take one contact for each potential ...
cubic theorist's user avatar
0 votes
0 answers
31 views

Natural communication problems that are hard only for number-in-hand protocols?

I am looking for tools to lower bound the deterministic, blackboard, number-in-hand communication complexity of a certain function which is roughly speaking $f : \{0,1\}^k \times \ldots \times \{0,1\}^...
Clay Thomas's user avatar
0 votes
0 answers
125 views

Is this graph communication game known?

Let $X_m=[m]=\{0,1,\dots,m-1\}$ and let $Y_m=[2m]\setminus [m]$. Given is a complete bipartite graph $G_m$, with parts $X_m$ and $Y_m$ and edges $\{x,y\}$ for every $x\in X_m$ and $y\in Y_m$. Alice ...
András Salamon's user avatar
-1 votes
1 answer
254 views

Reducing disjoint or indexing or inner-product problem to s-t connectivity problem in directed graph

I am asked to prove that an O(1)-pass randomized streaming algorithm that solves s-t connectivity problem in a simple directed graph $G=(V,E)$ with $|V|=n$ vertices, with sucess possibility $>\frac{...
Naketo's user avatar
  • 13
-1 votes
1 answer
79 views

Relationship between worst case length of transcript and entropy of transcript

Consider the two party model of communication complexity where Alice and Bob are given inputs $X$ and $Y$ sampled from some distribution $\mu$, and their goal is to solve some problem $P$ (the details ...
JohnDoe's user avatar
  • 11

1 2
3