Research map / Learning theory and algorithms / Sample complexity
Learning Multiple Secrets in Mastermind
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies Generalized Mastermind with multiple hidden secrets: gives a two-round randomized hypercube algorithm, round-adaptivity lower bounds, a deterministic sphere algorithm, and near-optimal hypercube algorithms with extra query characters.
Problem
Learning an unknown set H of n points in the hypercube {0,1}^d (or unit sphere) using nearest-point oracle queries, studying query complexity and the tradeoff with the number of adaptive rounds.
Approach
Extends Mastermind from one hidden code to a hidden set queried through a nearest-neighbor oracle; a two-round random-query-then-local-ball algorithm, a recursive XOR-based hard-distribution construction for r-round lower bounds, and convex-hull facet normal queries on the sphere.
Key results
- Two-round randomized algorithm for hypercube Generalized Mastermind uses 2^{O(sqrt(d log d log n))} queries.
- Any r-round randomized algorithm needs exp(Omega(d^{3^{-(r-1)}})) queries even with poly(d) points, so poly(d) queries require Omega(log log d) rounds.
- Deterministic algorithm on the unit sphere makes O(n^{floor(d/2)}) queries (stated for rank-k case as O(n^{floor(k/2)+1}+kd)); extra-character hypercube queries admit an O(nd) deterministic algorithm matching an Omega(nd/log d) lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a two-round adaptive algorithm with random first-round queries and local second-round queries | Generalized Mastermind with {0,1}^d queries · Hidden sets with n ≤ 2^{o(d/log d)} | query complexity: 2^{O(\sqrt{d \cdot \log d \cdot \log n})} | Helped |
| Limit the algorithm to r adaptive rounds | Randomized Generalized Mastermind with {0,1}^d queries · Hidden sets of size O(d^3) | query complexity: \exp({\Omega(d^{3^{-(r-1)}})}) | Hurt |
| Use the deterministic convex-hull algorithm | Continuous Generalized Mastermind on S^{d-1} · Hidden set of n points with rank k | query complexity: O(n^{\floor{\frac{k}{2}}+1} + kd ) | Helped |
| Allow queries from {0,1,2}^d rather than restricting queries to {0,1}^d | Generalized Mastermind · Hidden set H ⊆ {0,1}^d | query complexity: O(nd) | Helped |
| Use a deterministic algorithm with queries from {0,1,2}^d | Generalized Mastermind · Hidden set H ⊆ {0,1}^d | query complexity: O(nd) | Helped |
| Require a randomized algorithm to succeed with probability at least 2/3 | Generalized Mastermind with {0,1,2}^d queries · Hidden sets containing n points | query complexity: \Omega\left(\frac{nd}{\log d}\right) | Hurt |
Surprising findings
- Allowing extra characters in queries makes the hypercube problem much easier, reducing query complexity to near-linear in nd.
Limitations
- No polynomial-query algorithm known for the two-round or general hypercube setting.
- Sphere algorithm complexity n^{O(d)} is exponential in dimension and no nontrivial lower bound is known.
- Two-round algorithm's analysis requires n <= 2^{o(d/log d)}.
Experimental setup
Metrics: query complexity number of adaptive rounds
Builds on: Mastermind (Knuth, Chvatal) coin-weighing problem group testing
Closest papers by meaning
- The Query Complexity of Local Search in Rounds on General Graphs (NeurIPS 2026 · similarity 0.83)
- Robust Regression of General ReLUs with Queries (NeurIPS 2025 · similarity 0.82)
- On the Universal Near Optimality of Hedge in Combinatorial Settings (NeurIPS 2025 · similarity 0.81)
- Smoothed Agnostic Learning of Halfspaces over the Hypercube (NeurIPS 2025 · similarity 0.81)
- Optimal Algorithms for Learning Partitions with Faulty Oracles (NeurIPS 2024 · similarity 0.81)
- Active Learning of General Halfspaces: Label Queries vs Membership Queries (NeurIPS 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.