12 votes

Approximating the sign rank of a matrix

Recent work by Alon, Moran, and Yehudayoff gives an $O(n/\log n)$ approximation algorithm. Let $d$ be the VC-dimension of a sign matrix $S$. The idea is that there exists an efficiently computable ...
Sasho Nikolov's user avatar
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
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

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

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

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
  • 13.9k
7 votes
Accepted

One way communication complexity of multi exact matching

For the lower bound, consider the following problem: Alice is given $x \in \{0,1\}^n$ and Bob is given $i \in [n]$. Their goal is to output $x_i$ (in other words, they need to decide if $i$ is in the ...
Denis Pankratov'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
6 votes

Communication complexity problems with linear distance

Let $C:\{0,1\}^{n} \to \{0,1\}^{2n}$ be an error correcting code with linear distance. Let $g: \{0,1\}^{n} \times \{0,1\}^{n} \to \{0,1\}$ be a function whose randomized communication complexity is ...
Igor Shinkar's user avatar
  • 1,897
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

One way communication complexity of multi exact matching

One simple approach: Use a Bloom filter. Alice can construct a Bloom filter for the set of strings she has, and then send it to Bob. The Bloom filter will have size $O(cn)$ bits, and Bob's error ...
D.W.'s user avatar
  • 11.7k
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

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,451
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,164
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

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,350
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
  • 13.9k
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
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,393
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,350
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
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,350
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

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

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
  • 11.7k
3 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,350
2 votes

Problems still "hard" in the SMP/Referee model with shared randomness?

If A has a pointer (of length $\log n$) to a bit of B (whose input has length $n$), that requires, $\Theta(\log n)$ one-way communication, even with a public-coin. On the other hand, the referee needs ...
domotorp's user avatar
  • 13.9k

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