A Liar Game for Adaptive Covering Codes

Abstract

Covering codes, which are sets of Hamming balls which cover the discrete hypercube, have been studied in many settings, including betting on football pools with a fixed number of matches, so that a bet pays off if it correctly predicts enough matches.  There is even a code credited to Golay which appeared first in a Scandanavian football magazine!  We will discuss the modification called adaptivity, in which predictions are allowed to be made before each successive game is played.  We give, up to an absolute constant independent of the number of matches, the number of bets necessary to guarantee a payoff when a fixed number of predictions are allowed to be incorrect.  The proof involves a reformulation in terms of a 2-person perfect information zero-sum game, which in turn has a linear relaxation related to a random walk on the integers.  We discuss an application to data compression, and the implications of the result for error-correcting and covering codes and the sphere bound.  (This is joint work with Vadim Ponomarenko and Catherine Yan.)