The query complexity of finding a hidden permutation

DOI10.1007/978-3-642-40273-9_1MaRDI QIDQ2848962zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 3559318 (Why is no real title available?)
• Mastermind
• On the algorithmic complexity of the Mastermind game with black-peg results
• Randomization, derandomization and antirandomization: Three games
• Searching games with errors -- fifty years of coping with liars

Cited in

(13)

• Improved Approximation Algorithm for the Number of Queries Necessary to Identify a Permutation
• scientific article; zbMATH DE number 7651142 (Why is no real title available?)
• Exact learning of multitrees and almost-trees using path queries
• Permutation Property Testing under Different Metrics with Low Query Complexity
• Reducing the arity in unbiased black-box complexity
• Finding a hidden code by asking questions
• On the number of queries necessary to identify a permutation
• Solving static permutation mastermind using \(O(n \log n)\) queries
• Permuted puzzles and cryptographic hardness
• The query complexity of a permutation-based variant of mastermind
• From black-box complexity to designing new genetic algorithms
• The \((1+1)\) elitist black-box complexity of LeadingOnes
• The unbiased black-box complexity of partition is polynomial

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)