# The Query Complexity of a Permutation-Based Variant of Mastermind

arXiv: https://arxiv.org/abs/1812.08480 · HTML: https://mlsanity.com/paper/1812.08480/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Dec 2018.

## Built on by (most cited first, 4 of 4)

- [Theory-inspired Parameter Control Benchmarks for Dynamic Algorithm Configuration](https://mlsanity.com/paper/2202.03259/) (2022)
- [Choosing the Right Algorithm With Hints From Complexity Theory](https://mlsanity.com/paper/2109.06584/) (2021)
- [Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus](https://mlsanity.com/paper/2302.08021/) (2023)
- [Frequency Fitness Assignment: Optimization without Bias for Good Solutions can be Efficient](https://mlsanity.com/paper/2112.00229/) (2021)

## Abstract (arXiv)

We study the query complexity of a permutation-based variant of the guessing game Mastermind. In this variant, the secret is a pair (z,π) which consists of a binary string z ∈ 0,1n and a permutation π of [n]. The secret must be unveiled by asking queries of the form x ∈ 0,1n. For each such query, we are returned the score [ fz,π(x):= max  i ∈ [0..n]mid forall j ≤ i: zπ(j) = xπ(j),;] i.e., the score of x is the length of the longest common prefix of x and z with respect to the order imposed by π. The goal is to minimize the number of queries needed to identify (z,π). This problem originates from the study of black-box optimization heuristics, where it is known as the textscLeadingOnes problem. In this work, we prove matching upper and lower bounds for the deterministic and randomized query complexity of this game, which are Theta(n log n) and Theta(n log log n), respectively.