The two-batch liar game over an arbitrary channel

Ioana Dumitriu; Joel Spencer

doi:10.1137/040617510

The two-batch liar game over an arbitrary channel

Ioana Dumitriu, Joel Spencer

Research output: Contribution to journal › Article › peer-review

Abstract

We consider liar games in which player Paul must ask one full batch of questions, receive all answers, and then ask a second and final batch of questions. We show that the effect of this restriction is asymptotically negligible. The strategy for Paul is given explicitly.

Original language	English (US)
Pages (from-to)	1056-1064
Number of pages	9
Journal	SIAM Journal on Discrete Mathematics
Volume	19
Issue number	4
DOIs	https://doi.org/10.1137/040617510
State	Published - 2005

Keywords

Adaptive strategy
Asymptotics
Channel
Coding theory
Liar games

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1137/040617510

Cite this

@article{d03960f235aa44b9b18ec94babd00ac4,

title = "The two-batch liar game over an arbitrary channel",

abstract = "We consider liar games in which player Paul must ask one full batch of questions, receive all answers, and then ask a second and final batch of questions. We show that the effect of this restriction is asymptotically negligible. The strategy for Paul is given explicitly.",

keywords = "Adaptive strategy, Asymptotics, Channel, Coding theory, Liar games",

author = "Ioana Dumitriu and Joel Spencer",

year = "2005",

doi = "10.1137/040617510",

language = "English (US)",

volume = "19",

pages = "1056--1064",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

TY - JOUR

T1 - The two-batch liar game over an arbitrary channel

AU - Dumitriu, Ioana

AU - Spencer, Joel

PY - 2005

Y1 - 2005

N2 - We consider liar games in which player Paul must ask one full batch of questions, receive all answers, and then ask a second and final batch of questions. We show that the effect of this restriction is asymptotically negligible. The strategy for Paul is given explicitly.

AB - We consider liar games in which player Paul must ask one full batch of questions, receive all answers, and then ask a second and final batch of questions. We show that the effect of this restriction is asymptotically negligible. The strategy for Paul is given explicitly.

KW - Adaptive strategy

KW - Asymptotics

KW - Channel

KW - Coding theory

KW - Liar games

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

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

U2 - 10.1137/040617510

DO - 10.1137/040617510

M3 - Article

AN - SCOPUS:33751175427

SN - 0895-4801

VL - 19

SP - 1056

EP - 1064

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 4

ER -

The two-batch liar game over an arbitrary channel

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this