By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Discrete Mathematics

Previous Article
Sparse Distance Preservers and Additive Spanners
For an unweighted graph $G = (V,E)$, $G' = (V,E')$ is a subgraph if $E' \subseteq E$, and $G' = (V',E',\omega)$ is a Steiner graph if $V \subseteq V'$, and for any pair of vertices $u,w \in V$, the d...
Next Article
Bisubmodular Function Minimization
This paper presents the first combinatorial polynomial algorithm for minimizing bisubmodular functions, extending the scaling algorithm for submodular function minimization due to Iwata, Fleischer, a...

You are logged in to this journal.

The Two-Batch Liar Game over an Arbitrary Channel

SIAM J. Discrete Math. Volume 19, Issue 4, pp. 1056-1064 (2005)

Issue Date: 2005
FULL TEXT OPTIONS   (FREE)
Download PDF (143 kB) View Cart

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.

©2006 Society for Industrial and Applied Mathematics
Permalink: http://dx.doi.org/10.1137/040617510

KEYWORDS and AMS

Keywords
AMS Subject Classifications
91A05, 91A46, 94B25, 68R05, 68W01

PUBLICATION DATA

ISSN:
0895-4801 (print)   1095-7146 (online)
Publisher:
AIP is a member of CrossRef SIAM

REFERENCES (10)
View in Separate Window/Tab
  1. Noga Alon, Joel Spencer, The probabilistic method, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience [John Wiley & Sons], 2000xviii+301, With an appendix on the life and work of Paul Erdos [MathRev]
  2. E. Berlekamp, Block coding for the binary symmetric channel with noiseless, delayless feedback, John Wiley, New York, 1968, 61–88 [MathRev]
  3. F. Cicalese and D. Mundici, Optimal coding with one asymmetric error: Below the sphere packing bound, in Proceedings of the 6th Annual International Conference on Computing and Combinatorics–COCOON'2000, Lecture Notes in Comput. Sci., 1858, Springer-Verlag, 2000, pp. 159–169.
  4. Ioana Dumitriu, Joel Spencer, A Halfliar's game, Theoret. Comput. Sci., 313 (2004), 353–369, Algorithmic combinatorial game theory
  5. Ioana Dumitriu, Joel Spencer, The liar game over an arbitrary channel, Combinatorica, 25 (2005), 537–559
  6. Andrzej Pelc, Searching games with errors—fifty years of coping with liars, Theoret. Comput. Sci., 270 (2002), 71–109
  7. Alfréd Rényi, A diary on information theory, Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, John Wiley & Sons Ltd., 1987x+125, With a foreword by Pál Révész; Translated from the Hungarian by Zsuzsanna Makkai-Bencsáth Reprint of the 1984 edition [MathRev]
  8. Joel Spencer, Ulam's searching game with a fixed number of lies, Theoret. Comput. Sci., 95 (1992), 307–321
  9. Joel Spencer, Catherine Yan, The halflie problem, J. Combin. Theory Ser. A, 103 (2003), 69–89
  10. S. Ulam, Adventures of a mathematician, Charles Scribner's Sons, 1976xi+317 pp. (25 plates) [ZentralblattMath] [MathRev]