  The arbitrarily varying channel (AVC) is a channel model whose state is
selected maliciously by an adversary. Fixed-blocklength coding assumes a
worst-case bound on the adversary's capabilities, which leads to pessimistic
results. This paper defines a variable-length perspective on this problem, for
which achievable rates are shown that depend on the realized actions of the
adversary. Specifically, rateless codes are constructed which require a limited
amount of common randomness. These codes are constructed for two kinds of AVC
models. In the first the channel state cannot depend on the channel input, and
in the second it can. As a byproduct, the randomized coding capacity of the AVC
with state depending on the transmitted codeword is found and shown to be
achievable with a small amount of common randomness. The results for this model
are proved using a randomized strategy based on list decoding.
