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 ...
- 18k
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 ...
- 13.4k
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 ...
- 515
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$. ...
- 515
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 ...
- 18k
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 ...
- 18k
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 ...
- 26.5k
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\...
- 96
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 ...
- 131
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 ...
- 18k
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 ...
- 377
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 ...
- 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 ...
- 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$,
...
- 26.5k
6
votes
Low rank Log rank conjecture
Not that I am aware of. This is unknown even for special cases, e.g. XOR functions.
- 746
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 ...
- 18.7k
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 ...
- 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 ...
- 31.8k
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 ...
- 511
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 ...
- 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 ...
- 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$ ...
- 14.8k
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 ...
- 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 ...
- 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 ...
- 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 ...
- 515
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 ...
- 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 ...
- 18k
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 ...
- 368
Only top scored, non community-wiki answers of a minimum length are eligible