Skip to main content
Share Your Experience: Take the 2024 Developer Survey
8 votes
Accepted

0-partition number vs partition number

A quadratic separation between $\log\chi_0$ and $\log\chi_1$ is proved in a paper by Göös, Jayram, Pitassi and Watson, see the ECCC report. In Theorem 2 they construct a function $F$ with small $\log\...
Raskolnikov's user avatar
8 votes

Binary rank of binary matrix

This is equivalent to the biclique partition number of a bipartite graph. You can think of M as representing a bipartite graph $G$ on $[n] \times [m]$ in the natural way: $M_{i,j}$ is 1 if and only if ...
Sasho Nikolov's user avatar
8 votes
Accepted

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

After more than two years, I have to assume the answer is "no". (Posting this stub answer so the question can be marked as answered.)
8 votes
Accepted

How powerful is $ACC^0$ circuit class in average case?

There seem to be typos in what you wrote; I take it you're asking: is there a function $f \in NEXP$ such that for all polynomials $p$ and infinitely many $n$, no ACC0 circuit of $p(n)$ size can ...
Ryan Williams's user avatar
8 votes
Accepted

Randomized communication complexity of or-of-equalities

We can directly reduce Set Disjointness to OR of Equalities. (This immediately implies an $\Omega(n)$ lower bound.) I think the proof is basically folklore. For a vector $A$ and $B$ of length $n$, ...
Ryan Williams's user avatar
7 votes
Accepted

One-way randomized communication complexity of Greater-Than

If you look at the MNSW proof carefully, the base case can be taken to be the trivial fact that a $0$-round protocol for $\textrm{GT}_n$ with $n = 1$ requires one bit of communication. If the goal is ...
chax's user avatar
  • 158
7 votes
Accepted

Is there a name for this concept in Communication Complexity?

What you call $cc_{max}$ is known as the worst-case partition communication complexity, and what you call $cc_{min}$ is known as the best-case partition communication complexity. These have been ...
domotorp's user avatar
  • 14k
6 votes

Low rank Log rank conjecture

Not that I am aware of. This is unknown even for special cases, e.g. XOR functions.
Shachar Lovett's user avatar
5 votes
Accepted

Communication complexity of approximating the size of set intersection

I will give two upper bounds. Let $A$ and $B$ be the sets given to Alice and Bob, respectively, and put $a=|A|$, $b=|B|$, $c=|A\cap B|$. First, there is a randomized protocol that, given $d>0$ ...
Emil Jeřábek's user avatar
4 votes
Accepted

Gap-Hamming with different "threshold" (i.e., not $n/2$)

As it turns out, the one-sided error case (public coin) was addressed in [KK16], which shows the communication complexity is then $\tilde{\Theta}\!\left(\frac{(t-g)^2}{t+g}\right)$ (the upper and ...
Clement C.'s user avatar
  • 4,471
4 votes

Regular languages and constant communication complexity

For $\Rightarrow$, you have "Communication Complexity", Eyal Kushilevitz in Advances in Computers, Volume 44, 1997 (http://www.sciencedirect.com/science/article/pii/S0065245808603423). You can also ...
holf's user avatar
  • 2,174
4 votes

Methods for proving deterministic communication complexity lower bounds

One approach that's quite different from the ones you mention is proving communication complexity lower bounds by reductions to query complexity problems. This approach can give lower bounds which are ...
Sasho Nikolov's user avatar
4 votes
Accepted

Binary rank of binary matrix

I had the following recent paper giving an fpt algorithm for binary rank. Our algorithm checks whether the given matrix has binary rank $k$ in $\mathcal{O}(2^{3k^2})poly(n+m)$ time, and if yes it also ...
Davis Issac's user avatar
4 votes
Accepted

Expected vs worst-case communication complexity

The reason is that a lower bound on the worst-case complexity automatically implies a lower bound on the expected complexity, so there is no reason to prove the latter. To see the implication, ...
Or Meir's user avatar
  • 5,615
4 votes
Accepted

Newman's lemma for distributional communication complexity

There's nothing wrong in your proof, but you can do even better; by taking the average in $$ \mathbb{E}_r \mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r) \neq f(x,y)} \leq \varepsilon $$ you can conclude ...
domotorp's user avatar
  • 14k
4 votes
Accepted

Why not include private randomness in internal communication information definition?

I agree that the definition you suggest is more natural. However, this definition is equivalent to the definition without the private randomness, so I assume they omit the private randomness just to ...
Or Meir's user avatar
  • 5,615
4 votes
Accepted

Deterministic communication complexity of refinement

The deterministic communication complexity of the problem is $\Theta(n\log{n})$: it is sufficient to show the existance of a family $S$ of partitions such that $|S|= 2^{\Omega(n\log{n})}$ and that for ...
user3209423940248's user avatar
4 votes

What are the up-to-date results on explicit lower bounds for $\Sigma_2$ communication complexity?

This paper by Lokam shows a lower bound of $3\log n$ on the $\Sigma_2$-communication complexity of inner product and related functions: https://www.semanticscholar.org/paper/Graph-Complexity-and-Slice-...
Or Meir's user avatar
  • 5,615
3 votes
Accepted

Estimating inner product over $[r]^d$

In the indexing problem Alice has a vector $x \in \{0,1\}^d$ and Bob has a number $i$, and Bob wants to learn $x_i$. The randomized one-way communication complexity of this problem is $\Omega(d)$ (see ...
Sasho Nikolov's user avatar
3 votes
Accepted

Combination of Disjointness and Gap Hamming Distance communication complexity

Yes, because (1) KLLRX prove $\Omega(n)$ information lower bound for Gap Hamming (for distribution over both YES and NO inputs), and (2) Theorem 3 in GJPW shows any such information lower bound holds ...
Manabu Yukawa's user avatar
3 votes

One-way randomized communication complexity of Greater-Than

The Ph.D. thesis of Pranab Sen (http://www.tcs.tifr.res.in/~pgdsen/pages/phdthesis/thesis.pdf) provides a $\Omega(n^{1/t}t^{-2})$ lower bound for $t$ round bounded error CC for Greater-than. I think ...
withhighprob's user avatar
3 votes
Accepted

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

Suppose Alice always sends exactly $k$ bits to Bob during the protocol. On average, how many possible candidates for her $n$-bit string are consistent with the communication transcript? What does ...
D.W.'s user avatar
  • 12.1k
3 votes

Methods for proving deterministic communication complexity lower bounds

In addition to the ones you mentioned, a lower bound method in deterministic communication complexity that you can possibly add to your toolkit is norm based approaches as described in chapter 2, ...
Sidhanth Mohanty's user avatar
3 votes

Communication complexity of approximating the size of set intersection

[Emil's answer is clearly better and simpler if you're interested in this type of error, unless for some reason you need your protocol to be deterministic. Oops.] There are nontrivial protocols if ...
GMB's user avatar
  • 2,403
3 votes
Accepted

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

It is true that there is "no randomness" in the sense that the protocol is not randomized and is supposed to work on all inputs. However, that does not mean that we are not allowed to use probability ...
Or Meir's user avatar
  • 5,615
2 votes

Compressing information about the halting problem for oracle Turing machines

Let $J^A(e)$ be the output of the $e$th Turing machine equipped with oracle $A$, on input $e$. Here $J$ stands for "jump". (In case of non-halting, $J^A(e)$ is undefined.) An oracle $A$ is jump-...
Bjørn Kjos-Hanssen's user avatar
2 votes

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

It is big open problem to prove lower bounds. This would imply lower bounds for BP.PP communication protocols (e.g., Tarui's Theorem in communication complexity), which would then imply lower bounds ...
Tetsuya Ishigami's user avatar
2 votes

Complexity of Yao's tiling number?

When viewing the Boolean matrix as the bipartite adjacency matrix of a bipartite graph, the problem of determining $\chi_1(f)$, that is, partitioning all the $1$s of the matrix into monochromatic ...
Hermann Gruber's user avatar
2 votes

Nondeterministic communication complexity

The definition that uses a proof system works. The way to think about it is as if the prover sees the inputs of both parties and sends the same proof to both parties. Then, each party decides whether ...
Or Meir's user avatar
  • 5,615
1 vote
Accepted

Composition theorem for randomized communication complexity

My understanding is that it's not following from [Nisan94], but from [BCW98] (note that there are two citations provided from Theorem 5), specifically their Theorem 2.1. while phrased for quantum, ...
Clement C.'s user avatar
  • 4,471

Only top scored, non community-wiki answers of a minimum length are eligible