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

DOI10.1016/J.TCS.2019.12.028zbMATH Open1448.91005arXiv1708.08738OpenAlexW2997016319MaRDI QIDQ2290640FDOQ2290640

Authors: Ferdinando Cicalese, Massimiliano Rossi 

Publication date: 29 January 2020

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

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

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

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

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)

Cites Work

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

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)