Rounds in a combinatorial search problem

2016/11/30 by Gerbner, Dániel, Vizer, Máté · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1611.10133

Abstract

We consider the following combinatorial search problem: we are given some excellent elements of [n] and we should find at least one, asking questions of the following type: "Is there an excellent element in A ⊂ [n]?". G.O.H. Katona proved sharp results for the number of questions needed to ask in the adaptive, non-adaptive and two-round versions of this problem. We verify a conjecture of Katona by proving that in the r-round version we need to ask rn^1/r+O(1) queries for fixed r and this is sharp. We also prove bounds for the queries needed to ask if we want to find at least d excellent elements.

Cited by

• Finding one excellent element in case of one lie

Related

• Rounds in Combinatorial Search
• Searching, Sorting, and Cake Cutting in Rounds
• Cooperation in Combinatorial Search
• Learning Partitions with Optimal Query and Round Complexities
• A tight bound for the clique query problem in two rounds