I recently learned about the one-way 2-party model of communication complexity in some lecture notes. It seems that all algorithms studied in this model are either deterministic or randomized Monte Carlo, i.e., they fail with some nonzero error probability. This made me wonder if there is an obvious reason why we don't consider Las Vegas (i.e. 0-error) algorithms in the one-way setting:
- Does a lower bound $\Omega(c)$ bits for deterministic algorithms imply that $\Omega(c)$ bits are necessary (in expectation) even for Las Vegas algorithms, in the public coin one-way 2-party model of communication complexity?
It looks like this statement should be true (I'm not sure if it is!), simply because compressing the message size inevitably introduces some amount of error and since we are in the one-way model there is no way for Alice to rectify a (rare) bad event, e.g., by Bob asking Alice to send more bits.
- In case the answer to question 1 is "No": What would be an example of a Boolean function where the one-way deterministic communication complexity is asymptotically worse than the Las Vegas communication complexity?