The liar game over an arbitrary channel

Ioana Dumitriu; Joel Spencer

doi:10.1007/s00493-005-0033-3

The liar game over an arbitrary channel

Ioana Dumitriu, Joel Spencer

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	537-559
Number of pages	23
Journal	Combinatorica
Volume	25
Issue number	5
DOIs	https://doi.org/10.1007/s00493-005-0033-3
State	Published - Sep 2005

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-005-0033-3

Cite this

@article{d32aff5e7f4d4b94bc7a74e72ed4aba6,

title = "The liar game over an arbitrary channel",

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.",

author = "Ioana Dumitriu and Joel Spencer",

note = "Funding Information: Ioana Dumitriu would like to thank the Clay Mathematics Institute, as part of this research was done while she was a Special Project Prize Fellow of CMI, during the summer of 2002. Ioana Dumitriu{\textquoteright}s research was also partially supported from NSF grant DMS-9971591.",

year = "2005",

month = sep,

doi = "10.1007/s00493-005-0033-3",

language = "English (US)",

volume = "25",

pages = "537--559",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "5",

}

TY - JOUR

T1 - The liar game over an arbitrary channel

AU - Dumitriu, Ioana

AU - Spencer, Joel

N1 - Funding Information: Ioana Dumitriu would like to thank the Clay Mathematics Institute, as part of this research was done while she was a Special Project Prize Fellow of CMI, during the summer of 2002. Ioana Dumitriu’s research was also partially supported from NSF grant DMS-9971591.

PY - 2005/9

Y1 - 2005/9

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

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

UR - http://www.scopus.com/inward/record.url?scp=33646172754&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646172754&partnerID=8YFLogxK

U2 - 10.1007/s00493-005-0033-3

DO - 10.1007/s00493-005-0033-3

M3 - Article

AN - SCOPUS:33646172754

SN - 0209-9683

VL - 25

SP - 537

EP - 559

JO - Combinatorica

JF - Combinatorica

IS - 5

ER -

The liar game over an arbitrary channel

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this