Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Doerr, Benjamin
Lengler, Johannes
Steurer, Daniel

dblp
dblp
dblp

Not MPG Author(s):

Lengler, Johannes
Steurer, Daniel

Editor(s):

Asano, Tetsuo

dblp

Not MPII Editor(s):

Asano, Tetsuo

BibTeX cite key*:

IntLiar2006

Title, Booktitle

Title*:

The Interval Liar Game

Booktitle*:

Algorithms and Computation : 17th International Symposium, ISAAC 2006

Event, URLs

URL of the conference:


URL for downloading the paper:

http://www.springerlink.com/content/g1154222g2234610/fulltext.pdf

Event Address*:

Kolkata, India

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

18 December 2006

Event End Date:

20 December 2006

Publisher

Name*:

Springer

URL:

http://www.springer.com/

Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

4288

Number:


Month:


Pages:

318-327

Year*:

2006

VG Wort Pages:

19

ISBN/ISSN:

3-540-49694-6

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

We regard the problem of communication in the presence of faulty
transmissions. In contrast to the classical works in this area, we assume some
structure on the times when the faults occur. More realistic seems the model that
all faults occur in some small time interval.
Like previous work, our problem can best be modelled as a two-player perfect
information game, in which one player (“Paul”) has to guess a number x from
{1, . . . , n} using Yes/No-questions, which the second player (“Carole”) has to
answer truthfully apart from few lies. In our setting, all lies have to be in a consecutive
set of k rounds.
We show that Paul needs roughly log n + log log n + k rounds to determine the
number, which is only k more than the case of just one single lie.

URL for the Abstract:

http://www.springerlink.com/content/g1154222g2234610/



Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{IntLiar2006,
AUTHOR = {Doerr, Benjamin and Lengler, Johannes and Steurer, Daniel},
EDITOR = {Asano, Tetsuo},
TITLE = {The Interval Liar Game},
BOOKTITLE = {Algorithms and Computation : 17th International Symposium, ISAAC 2006},
PUBLISHER = {Springer},
YEAR = {2006},
VOLUME = {4288},
PAGES = {318--327},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Kolkata, India},
ISBN = {3-540-49694-6},
}


Entry last modified by Regina Kraemer, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Mathias Bader
Created
11/24/2006 01:21:56 PM
Revisions
12.
11.
10.
9.
8.
Editor(s)
Regina Kraemer
Anja Becker
Uwe Brahm
Uwe Brahm
Uwe Brahm
Edit Dates
08/28/2008 08:59:06 AM
25.02.2008 08:52:04
07/07/2007 00:44:37
04/25/2007 10:37:20 AM
04/25/2007 10:37:01 AM