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

(14)

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

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)