论文标题
关于大量查询大小的非自适应多数问题
On non-adaptive majority problems of large query size
论文作者
论文摘要
我们得到了$ n $ balls和两种颜色的未知色彩。我们的目标是找到一个属于较大颜色类别的球，或者表明颜色类具有相同的大小。我们可以将$ k $ balls的集合作为查询，并且根据查询的答案是什么，问题具有不同的变体。这些问题吸引了几个研究人员，但是大多数研究的重点是自适应版本，在学习了上一篇查询的答案后，在其中依次确定查询。在这里，我们研究了非自适应版本，必须同时询问所有查询。
We are given $n$ balls and an unknown coloring of them with two colors. Our goal is to find a ball that belongs to the larger color class, or show that the color classes have the same size. We can ask sets of $k$ balls as queries, and the problem has different variants, according to what the answers to the queries can be. These questions has attracted several researchers, but the focus of most research was the adaptive version, where queries are decided sequentially, after learning the answer to the previous query. Here we study the non-adaptive version, where all the queries have to be asked at the same time.
