# Tag Info

## Hot answers tagged communication-complexity

3

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, observe that every randomized protocol with expected complexity $c$ and error probability $\varepsilon$ can be transformed into a randomized protocol with worst-case ...

1

Here is a fairly recent paper by Balcan et. al. from SODA'19 that gives a sample-optimal algorithm to test matrix rank. Note, in the query complexity setting, you need to have an appropriate notion of gap, which is exactly what they consider here. The paper should also list most of the relevant references.

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