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 ...
- 18.1k
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
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 ...
- 18.1k
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 ...
- 27.3k
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$,
...
- 27.3k
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.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 ...
- 377
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
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
6
votes
Low rank Log rank conjecture
Not that I am aware of. This is unknown even for special cases, e.g. XOR functions.
- 756
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$ ...
- 16.9k
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 ...
- 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 ...
- 368
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,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 ...
- 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 ...
- 18.1k
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, ...
- 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 ...
- 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 ...
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 ...
- 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 ...
- 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 ...
- 131
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 ...
- 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 ...
- 18.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, ...
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 ...
- 345
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 ...
- 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-...
- 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 ...
- 13.9k
Only top scored, non community-wiki answers of a minimum length are eligible