Searching games with errors -- fifty years of coping with liars

DOI10.1016/S0304-3975(01)00303-6zbMath0984.68041OpenAlexW2044712489WikidataQ56039267 ScholiaQ56039267MaRDI QIDQ5958303

Andrzej Pelc

Publication date: 3 March 2002

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00303-6

zbMATH Keywords

gamestrategysearchingerrorLie

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (60)

Strategies for the Renyi--Ulam game with fixed number of lies ⋮ Typical rounding problems ⋮ European tenure games ⋮ A halfliar's game ⋮ Unnamed Item ⋮ Complexity of question/answer games ⋮ \(Q\)-ary search with one Lie and bi-interval queries ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Continuous guessing games with two secret numbers ⋮ Product logic and probabilistic Ulam games ⋮ Optimal Dislocation with Persistent Errors in Subquadratic Time ⋮ Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees ⋮ On the Rényi-Ulam game with restricted size queries ⋮ The halflie problem. ⋮ Minimum average-case queries of \(q+1\)-ary search game with small sets ⋮ \(Q\)-ary Rényi-Ulam pathological liar game with one lie ⋮ Open Problems on Search Games ⋮ External-memory sorting with comparison errors ⋮ Perfect minimally adaptive \(q\)-ary search with unreliable tests ⋮ Recursive merge sort with erroneous comparisons ⋮ Designing reliable algorithms in unreliable memories ⋮ Propositional dynamic logic for searching games with errors ⋮ Computing majority via multiple queries ⋮ Perfect strategies for the Ulam-Rényi game with multi-interval questions ⋮ Binary search in graphs revisited ⋮ Searching a Tree with Permanently Noisy Advice ⋮ Searching with lies under error cost constraints ⋮ Optimal dislocation with persistent errors in subquadratic time ⋮ The Rényi-Ulam games and many-valued logics ⋮ A simple solution to Ulam's liar game with one lie ⋮ Resilient dynamic programming ⋮ How to play the majority game with a liar ⋮ On searching strategies, parallel questions, and delayed answers ⋮ Rényi-Ulam Game Semantics for Product Logic and for the Logic of Cancellative Hoops ⋮ Unnamed Item ⋮ Finding the maximum and minimum elements with one lie ⋮ Minimal average cost of searching for a counterfeit coin: restricted model ⋮ Searching for a counterfeit coin with \(b\)-balance ⋮ Least adaptive optimal search with unreliable tests ⋮ How to play the one-lie Rényi-Ulam game ⋮ Rényi-Berlekamp-Ulam searching game with bi-interval queries and two lies ⋮ On the multi-interval Ulam-Rényi game: for 3 lies 4 intervals suffice ⋮ A Combinatorial Model of Two-Sided Search ⋮ Minimum number of queries for an adaptive liar search game with small sets ⋮ Sorting and searching in faulty memories ⋮ Binary search with delayed and missing answers ⋮ Resilient Dictionaries for Randomly Unreliable Memory ⋮ The price of resiliency: a case study on sorting with memory faults ⋮ An Asymptotic Solution of Dresher’s Guessing Game ⋮ Approximate minimum selection with unreliable comparisons ⋮ Optimal resilient sorting and searching in the presence of memory faults ⋮ Binary Search in Graphs Revisited ⋮ Searching for a counterfeit coin with two unreliable weighings ⋮ The Query Complexity of Finding a Hidden Permutation ⋮ The Rényi-Ulam pathological liar game with a fixed number of lies ⋮ Unnamed Item ⋮ Truth tellers and liars with fewer questions ⋮ Searching with lies under error transition cost constraints ⋮ The Interval Liar Game ⋮ Sorting with Recurrent Comparison Errors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• Binary search with errors and variable cost queries
• Fault-tolerant search algorithms. Reliable computation with unreliable information
• An algorithm for ``Ulam's Game and its application to error correcting codes
• Finding the maximum and minimum
• Ulam's searching game with two lies
• Searching with a forbidden lie pattern in responses
• Coping with known patterns of lies in a search game
• Sorting in \(c \log n\) parallel steps
• Lie patterns in search procedures
• Solution of Ulam's problem on searching with a lie
• Prefix search with a lie
• Solution of Ulam's problem on binary search with two lies
• Searching with known error probability
• Detecting errors in searching games
• Ulam's searching game with lies
• Weakly adaptive comparison searching
• Coping with errors in binary search procedures
• Ulam's searching game with a fixed number of lies
• Solution of Ulam's problem on binary search with three lies
• Searching with lies: The Ulam problem
• On sorting in the presence of erroneous information
• An almost optimal algorithm for unbounded searching
• Group testing with unreliable tests
• Information availability vs. solution space size in a knowledge acquisition problem
• Logic of infinite quantum systems
• Searching with local constraints on error patterns
• A nonadaptive version of Ulam's problem with one lie
• Optimal comparison strategies in Ulam's searching game with two errors
• Perfect two-fault tolerant search with minimum adaptiveness
• Solution of Ulam's searching game with three lies or an optimal adaptive strategy for binary three-error-correcting codes
• Playing by searching: Two strategies against a linearly bounded liar
• An improved heuristic for the ``Ulam-Rényi game
• Ulam's searching game with three lies
• Ulam's liar problem
• Searching with lies
• Conditioning a state by a Łukasiewicz event: a probabilistic approach to Ulam games
• Optimal strategies against a liar
• Locating Information with Uncertainty in Fully Interconnected Networks with Applications to World Wide Web Information Retrieval
• On Fault-Tolerant Networks for Sorting
• Guess a Number-with Lying
• Unbounded Searching Algorithms
• Coding Theory Applied to a Problem of Ulam
• Fault Tolerant Sorting Networks
• Three Thresholds for a Liar
• Effective Search Problems
• On boolean decision trees with faulty nodes
• Computing with Noisy Information
• Error Detecting and Error Correcting Codes
• Generalized Kraft’s Inequality and Discrete k-Modal Search
• ON EVALUATING BOOLEAN FUNCTIONS WITH UNRELIABLE TESTS
• Comparison-based search in the presence of errors
• Optimization of Reduced Dependencies for Synchronous Sequential Machines
• A class of simple and optimal strategies for block coding on the binary symmetric channel with noiseless feedback
• Fault-tolerant broadcasting and gossiping in communication networks
• Search with small sets in presence of a liar

This page was built for publication: Searching games with errors -- fifty years of coping with liars