Las Vegas vs Deterministic in one-way communication complexity

Question

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:

1. 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.

2. 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?

Answer 1

First, let's describe the one-way model of communication, for computing a function $f$ on Alice's input $x$ and Bob's input $y$:

• Alice sends Bob a string $s$ depending on $x$.
• Bob broadcasts the value of $f(x,y)$.

Alice could be a probabilistic algorithm, and in that case, Bob might sometimes output the wrong answer. To make the task nontrivial, for each $x$, Bob should output the correct answer with probability $2/3$. The cost of the protocol is the maximum length of $s$, over all possible $x$ and coin tosses.

There are actually two different variants of this model. The model just described has private coins: Bob only gets to see the string $s$. Another variant has public coins: the string that Alice sends is a function of both $s$ and some randomness $r$ not depending on $x$, and Bob gets to see both Alice's message $s$ and the randomness $r$ used to generate it.

(There's actually one more nicety: is the string $s$ self-delimiting or not? We can convert a protocol of cost $C$ to a self-delimiting protocol of cost $C + O(\log C)$, so the difference is not significant.)

---

How would a Las Vegas algorithm look like? Bob should now always output the correct answer, and the cost of the protocol is the maximum, over $x$, of the average length of $s$.

Consider first the private coin model. Suppose that cost of such a protocol is $C$. This means that for every input $x$, there is a string $s$ of length at most $C$ which causes Bob to output $f(x,y)$ correctly. Hence we can convert this protocol to a deterministic protocol with the same cost.

Newman's theorem shows that we can convert a protocol in the public coin model to one in the private coin model at an additive cost of $O(\log n)$, thereby converting a public coin protocol of cost $C$ to a deterministic protocol of cost $C + O(\log n)$.

---

In the presence of interaction, Las Vegas protocols become nontrivial, since Bob can single to Alice that she should "try again". Since no such feedback mechanism is available in the one-way model, Las Vegas algorithms don't really make sense in that model.