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 ...
user avatar
10 votes
Accepted

Deterministic communication complexity vs partition number

This question has just been resolved! As I mentioned, it was known that $Pn(f) \leq D(f) \leq (Pn(f))^2$, but it was a major open problem to show that either $Pn(f) = \Theta(D(f))$ or that there ...
user avatar
10 votes

Research problems in communication complexity

I'll start with answers to your general questions, then give one nice open problem with applications towards circuit complexity. It's hard to say what areas a new communication complexity researcher ...
user avatar
9 votes
Accepted

Nondeterministic communication complexity of set disjointness?

$N^1(DISJ_n) \geq n$. The fooling set technique actually provides lower bounds on the cover number. $C^1(f)$ is the minimum number of monochromatic rectangles needed to cover the $1$-inputs of $f$. ...
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 ...
user avatar
8 votes
Accepted

On the notion of positive rank of a matrix

There are examples of $n\times n$ real matrices of rank at most $3$ and non-negative rank at least $\sqrt{2n}$. So the non-negative rank cannot be bounded by any function of the rank in general. The ...
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 ...
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\...
user avatar
7 votes
Accepted

A direct-sum theorem for the non-deterministic communication complexity of inequality?

I think this can be done with $\log n \cdot\log t + t \cdot\log\log t$ bits of nondeterministic communication. By encoding all strings with an error correcting code, we may assume that whenever we ...
user avatar
7 votes
Accepted

One-way randomized communication complexity of approximate Hamming distance

Here is a simple protocol for Hamming distance that uses $O(\varepsilon^{-2} \log n)$ bits. The protocol is essentially the Alon, Matias, Szegedy second moment sketch. Or you can think of it as a ...
user avatar
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 ...
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 ...
user avatar
  • 13.5k
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 ...
user avatar
  • 158
7 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$, ...
user avatar
6 votes

Low rank Log rank conjecture

Not that I am aware of. This is unknown even for special cases, e.g. XOR functions.
user avatar
6 votes

Research problems in communication complexity

Several long-standing key open problems are in the Kushilevitz and Nisan textbook (see also the list of errata which mentions that Open Problem 8.6 was solved by Dietzfelbinger). Razborov's 2011 ...
user avatar
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 ...
user avatar
  • 1,897
5 votes

One-way randomized communication complexity of approximate Hamming distance

The lower bound problem you're looking for is the GAP-HAMMING problem. Sherstov has a "simplest" result for the general communication complexity of GAP HAMMING, and in his paper he has a nice review ...
user avatar
5 votes

Communication problems for which a deterministic direct-sum theorem is not known to hold

I think I can suggest the problem, which is not widely known, but for which I'm interested in. Suppose we have $n$ permutations $\pi_i$ in $S_3$. Alice, Bob and Carol receive first, second and third ...
user avatar
5 votes

Information complexity of query algorithms?

Yes, information theory is useful for proving lower bounds on the query complexity of problems in Computer Science. Alexander Golynski gave a good example in his ground breaking paper titled "Cell ...
user avatar
  • 2,511
5 votes
Accepted

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

It seems to me that there is some incoherency in the question. What do you mean by better? Are you looking for a function where $N(f) \ll D(f)$ or a function where $D(f) \ll N(f)$? Deterministic ...
user avatar
  • 21.3k
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$ ...
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 ...
user avatar
  • 4,341
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 ...
user avatar
  • 10.5k
4 votes

On the notion of positive rank

This is not an answer, but another version, NOT equivalent to the original of this excellent, but perhaps hard to grasp question. Define the bipartite clique partition number of a graph as the least ...
user avatar
  • 13.5k
4 votes
Accepted

On connecting combinatorial rectangles

It's not possible. Consider the following 3x3 boolean matrix: 1 1 0 1 0 1 0 1 1 For every pair of rows {r,r'} , there exists a column c such that {r,r'} X {c} is a combinatorial rectangle. For ...
user avatar
4 votes
Accepted

Classification of a specific problem

Let $\mathsf{coIP}$ denote the problem of returning the negation of the inner product. It has roughly the same complexity as $\mathsf{IP}$ since we can add to both players an extra $1$ bit. It is ...
user avatar
  • 14.1k
4 votes

Partition Number of a Matrix

The log of the partition number is a lower bound on the deterministic communication complexity and the square of the log of the partition number is an upper bound. In other words, if $CC$ is the ...
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 ...
user avatar

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