The query complexity of a permutation-based variant of Mastermind

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Peyman Afshani
  • Manindra Agrawal, Indian Institute of Technology Kanpur
  • ,
  • Benjamin Doerr, Laboratoire d'Informatique (LIX)
  • ,
  • Carola Doerr, Sorbonne Université
  • ,
  • Kasper Green Larsen
  • Kurt Mehlhorn, Max Planck Institute for Informatics

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,1} n and a permutation π of [n]. The secret must be unveiled by asking queries of the form x∈{0,1} n . For each such query, we are returned the score f z,π (x)≔max{i∈[0.n]∣∀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 LEADINGONES problem. In this work, we prove matching upper and lower bounds for the deterministic and randomized query complexity of this game, which are Θ(nlogn) and Θ(nloglogn), respectively.

Original languageEnglish
JournalDiscrete Applied Mathematics
Volume260
Pages (from-to)28-50
Number of pages23
ISSN0166-218X
DOIs
Publication statusPublished - May 2019

    Research areas

  • Black-box complexity, Hidden permutation, LEADINGONES, Query complexity

See relations at Aarhus University Citationformats

ID: 150885992