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.

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.

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.

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.

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

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.

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.

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.

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.