The liar game over an arbitrary channel

Ioana Dumitriu, Joel Spencer

Research output: Contribution to journalArticlepeer-review

Abstract

We introduce and analyze a liar game in which t-ary questions are asked and the responder may lie at most k times. As an additional constraint, there is an arbitrary but prescribed list (the channel) of permissible types of lies. For any fixed t, k, and channel, we determine the exact asymptotics of the solution when the number of queries goes to infinity.

Original languageEnglish (US)
Pages (from-to)537-559
Number of pages23
JournalCombinatorica
Volume25
Issue number5
DOIs
StatePublished - Sep 2005

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'The liar game over an arbitrary channel'. Together they form a unique fingerprint.

Cite this