Optimal schemes for combinatorial query problems with integer feedback

DOI10.5070/C63261997zbMATH Open1530.91109arXiv2203.09496OpenAlexW4386744372MaRDI QIDQ6138906FDOQ6138906

Anders Martinsson

Publication date: 16 December 2023

Published in: Combinatorial Theory (Search for Journal in Brave)

Abstract: A query game is a pair of a set $Q$ of queries and a set $mathcalF$ of functions, or codewords $f:QightarrowmathbbZ.$ We think of this as a two-player game. One player, Codemaker, picks a hidden codeword $finmathcalF$. The other player, Codebreaker, then tries to determine $f$ by asking a sequence of queries $qinQ$, 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 $Theta(nlogk/logn+k)$ if only black-peg information is provided, and $Theta(nlogk/logn+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 $kgeq{n}^{1-o(1)}$.

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

Recommendations

• Combinatorial algorithms for feedback problems in directed graphs
• Approximating incremental combinatorial optimization problems
• scientific article
• Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
• On Approximate Solutions for Combinatorial Optimization Problems
• Combinatorial \(n\)-fold integer programming and applications
• Combinatorial \(n\)-fold integer programming and applications
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Improved algorithms for feedback vertex set problems

zbMATH Keywords

query complexitycombinatorial gamesmastermindcoin-weighing

Mathematics Subject Classification ID

2-person games (91A05) Combinatorial games (91A46) Communication complexity, information complexity (68Q11)

Cites Work

• Title not available (Why is that?)
• Determination of a Subset from Certain Combinatorial Properties
• On Metric Generators of Graphs
• Coding for T-user multiple-access channels
• Mastermind
• On a Combinatorial Problem in Number Theory
• Title not available (Why is that?)
• Optimal reconstruction of graphs under the additive model
• On the algorithmic complexity of the Mastermind game with black-peg results
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the metric dimension of Cartesian powers of a graph
• The number of pessimistic guesses in generalized black-peg mastermind
• Playing Mastermind With Many Colors
• Title not available (Why is that?)

This page was built for publication: Optimal schemes for combinatorial query problems with integer feedback

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6138906)