Learning Multiple Secrets in Mastermind
Authors: Milind Prabhu, David Woodruff
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give a two-round adaptive algorithm for this problem that learns H while making at most exp( e O( d log n)) queries. Furthermore, we show that any r-round adaptive randomized algorithm that learns H with constant probability must make exp(Ω(d3 (r 1))) queries even when the input has poly(d) points; thus, any poly(d) query algorithm must necessarily use Ω(log log d) rounds of adaptivity. We give optimal query complexity bounds for the variant of the problem where queries are allowed to be from {0, 1, 2}d. We also study a continuous variant of the problem in which H is a subset of unit vectors in Rd, and one can query unit vectors in Rd. For this setting, we give an O(n d/2 ) query deterministic algorithm to learn the hidden set of points. |
| Researcher Affiliation | Academia | 1Department of Computer Science and Engineering, University of Michigan 2Department of Computer Science, Carnegie Mellon University. |
| Pseudocode | Yes | Algorithm 1 Two-Round Adaptive Algorithm; Algorithm 2 Deterministic Algorithm for Points on Sd 1.; Algorithm 3 A Deterministic Algorithm for the Stronger Query Model. |
| Open Source Code | No | The paper does not provide any specific statement about releasing source code, nor does it include links to a code repository. |
| Open Datasets | No | This is a theoretical paper that focuses on algorithm design and complexity analysis. It does not involve empirical experiments with training datasets. |
| Dataset Splits | No | This is a theoretical paper that focuses on algorithm design and complexity analysis. It does not involve empirical experiments with validation datasets or splits. |
| Hardware Specification | No | This is a theoretical paper focusing on algorithm design and complexity analysis, not empirical experiments. Therefore, no hardware specifications are mentioned for running experiments. |
| Software Dependencies | No | This is a theoretical paper that presents algorithms and complexity analysis. It does not describe any specific software implementations or list software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper focusing on algorithm design and complexity analysis. It does not involve empirical experiments, and thus no experimental setup details like hyperparameters or training settings are provided. |