The query complexity of finding a hidden permutation

DOI10.1007/978-3-642-40273-9_1zbMATH Open1391.68044OpenAlexW1526420097MaRDI QIDQ2848962FDOQ2848962

Authors: Peyman Afshani, Benjamin Doerr, Carola Doerr, Kasper Green Larsen, K. Mehlhorn, Manindra Agrawal 

Publication date: 13 September 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/11858/00-001M-0000-0025-0634-2

Recommendations

• The query complexity of a permutation-based variant of mastermind
• On the number of queries necessary to identify a permutation
• The exact query complexity of yes-no permutation mastermind
• The query complexity of order-finding
• Quantum queries on permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Mastermind
• Searching games with errors -- fifty years of coping with liars
• On the algorithmic complexity of the Mastermind game with black-peg results
• Title not available (Why is that?)
• Randomization, derandomization and antirandomization: Three games
• Playing Mastermind With Many Colors

Cited In (11)

• The \((1+1)\) elitist black-box complexity of LeadingOnes
• Solving static permutation mastermind using \(O(n \log n)\) queries
• The query complexity of a permutation-based variant of mastermind
• Improved Approximation Algorithm for the Number of Queries Necessary to Identify a Permutation
• The unbiased black-box complexity of partition is polynomial
• From black-box complexity to designing new genetic algorithms
• Permutation Property Testing under Different Metrics with Low Query Complexity
• Reducing the arity in unbiased black-box complexity
• Title not available (Why is that?)
• Exact learning of multitrees and almost-trees using path queries
• On the number of queries necessary to identify a permutation

This page was built for publication: The query complexity of finding a hidden permutation

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