On the multi-interval Ulam-Rényi game: for 3 lies 4 intervals suffice

DOI10.1016/J.TCS.2019.12.028MaRDI QIDQ2290640zbMATH OpenOpenAlexFDO

Authors Ferdinando Cicalese, Massimiliano Rossi

Publication date 29 January 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.08738

zbMATH Keywords

error correcting codesspace efficiencysearch with liesUlam-Rényi game

Mathematics Subject Classification ID

Applications of game theory (91A80) Measures of information, entropy (94A17) 2-person games (91A05)

Abstract: We study the problem of identifying an initially unknown $m$-bit number by using yes-no questions when up to a fixed number $e$ of the answers can be erroneous. In the variant we consider here questions are restricted to be the union of up to a fixed number of intervals. For any $egeq1$ let $k_e$ be the minimum $k$ such that for all sufficiently large $m$, there exists a strategy matching the information theoretic lower bound and only using $k$-interval questions. It is known that $k_e=O(e^2)$. However, it has been conjectured that the $k_e=Theta(e).$ This linearity conjecture is supported by the known results for small values of $e$. For $eleq2$ we have $k_e=e.$ We extend these results to the case $e=3$. We show $k_{3}leq4$ improving upon the previously known bound $k_{3}leq10.$

Recommendations

• Perfect strategies for the Ulam-Rényi game with multi-interval questions
• Q-ary Ulam-Rényi game with constrained lies
• Strategies for the Renyi--Ulam game with fixed number of lies
• Q-Ary Ulam-Renyi Game with Constrained Lies
• scientific article; zbMATH DE number 782050

Cites work

• scientific article; zbMATH DE number 1577986 (Why is no real title available?)
• scientific article; zbMATH DE number 4047591 (Why is no real title available?)
• scientific article; zbMATH DE number 3547240 (Why is no real title available?)
• scientific article; zbMATH DE number 3205803 (Why is no real title available?)
• Dealing with liars: misbehavior identification via Rényi-Ulam games
• Fault-tolerant search algorithms. Reliable computation with unreliable information
• Guess a Number-with Lying
• How to use expert advice
• Optimal comparison strategies in Ulam's searching game with two errors
• Parallel algorithms for select and partition with noisy comparisons
• Perfect strategies for the Ulam-Rényi game with multi-interval questions
• Recent developments of feedback coding and its relations with many-valued logic
• Searching games with errors -- fifty years of coping with liars
• Two Batch Search With Lie Cost
• Ulam's searching game with a fixed number of lies
• Ulam's searching game with lies
• Ulam's searching game with three lies
• Ulam's searching game with two lies

Cited in

(1)

• Perfect strategies for the Ulam-Rényi game with multi-interval questions

This page was built for publication: On the multi-interval Ulam-Rényi game: for 3 lies 4 intervals suffice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2290640)