论文标题
与整数反馈的组合查询问题的最佳方案
Optimal schemes for combinatorial query problems with integer feedback
论文作者
论文摘要
查询游戏是一对$ q $的查询$ q $，函数的$ \ MATHCAL {f} $，或codeWords $ f：q \ rightarrow \ rightarrow \ mathbb {z}。$我们认为这是两种玩家游戏。一个播放器，CodeMaker，在\ Mathcal {F} $中选择一个隐藏的CodeWord $ f \。然后，另一个播放器，代码breaker，试图通过询问Q $中的一系列查询$ q \来确定$ f $，在每个CodeMaker都必须以$ f（q）$的值响应之后。 CodeBreaker的目标是使用尽可能少的查询来唯一确定$ f $。此类游戏的两个经典示例是用春季和策划者进行硬币奖，这既是娱乐游戏，又是与信息理论的联系。 在本文中，我们将提出一个通用框架，以查找查询游戏的简短解决方案。作为应用程序，我们给出了新的独立的自给自足的证据，证明了硬币转换问题的变化的复杂性，并证明了新的结果表明，策划者与$ n $位置的确定性查询复杂性和$ k $ colors和$ k $ colors是$θ（n \ log k/ \ log k/ \ log n + k）$，如果仅提供了黑色log/ $ n \ k/ k/ n \ k/ k/ k/ k/ k/ k/ k $ n \ k/ flack/ n \ k/提供了白色PEG信息。在确定性的设置中，这些是第一个以任何$ k \ geq n^{1-o（1）} $而闻名的策划策略的常数最佳解决方案。
A query game is a pair of a set $Q$ of queries and a set $\mathcal{F}$ of functions, or codewords $f:Q\rightarrow \mathbb{Z}.$ We think of this as a two-player game. One player, Codemaker, picks a hidden codeword $f\in \mathcal{F}$. The other player, Codebreaker, then tries to determine $f$ by asking a sequence of queries $q\in Q$, after each of which Codemaker must respond with the value $f(q)$. The goal of Codebreaker is to uniquely determine $f$ using as few queries as possible. Two classical examples of such games are coin-weighing with a spring scale, and Mastermind, which are of interest both as recreational games and for their connection to information theory. In this paper, we will present a general framework for finding short solutions to query games. As applications, we give new self-contained proofs of the query complexity of variations of the coin-weighing problems, and prove new results that the deterministic query complexity of Mastermind with $n$ positions and $k$ colors is $Θ(n \log k/ \log n + k)$ if only black-peg information is provided, and $Θ(n \log k / \log n + k/n)$ if both black- and white-peg information is provided. In the deterministic setting, these are the first up to constant factor optimal solutions to Mastermind known for any $k\geq n^{1-o(1)}$.
