License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.1
URN: urn:nbn:de:0030-drops-112165
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11216/
Fernández V, Manuel ;
Woodruff, David P. ;
Yasuda, Taisuke
The Query Complexity of Mastermind with l_p Distances
Abstract
Consider a variant of the Mastermind game in which queries are l_p distances, rather than the usual Hamming distance. That is, a codemaker chooses a hidden vector y in {-k,-k+1,...,k-1,k}^n and answers to queries of the form ||y-x||_p where x in {-k,-k+1,...,k-1,k}^n. The goal is to minimize the number of queries made in order to correctly guess y.
In this work, we show an upper bound of O(min{n,(n log k)/(log n)}) queries for any real 1<=p<infty and O(n) queries for p=infty. To prove this result, we in fact develop a nonadaptive polynomial time algorithm that works for a natural class of separable distance measures, i.e., coordinate-wise sums of functions of the absolute value. We also show matching lower bounds up to constant factors, even for adaptive algorithms for the approximation version of the problem, in which the problem is to output y' such that ||y'-y||_p <= R for any R <= k^{1-epsilon}n^{1/p} for constant epsilon>0. Thus, essentially any approximation of this problem is as hard as finding the hidden vector exactly, up to constant factors. Finally, we show that for the noisy version of the problem, i.e., the setting when the codemaker answers queries with any q = (1 +/- epsilon)||y-x||_p, there is no query efficient algorithm.
BibTeX - Entry
@InProceedings{fernndezv_et_al:LIPIcs:2019:11216,
author = {Manuel Fern{\'a}ndez V and David P. Woodruff and Taisuke Yasuda},
title = {{The Query Complexity of Mastermind with l_p Distances}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {1:1--1:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11216},
URN = {urn:nbn:de:0030-drops-112165},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.1},
annote = {Keywords: Mastermind, Query Complexity, l_p Distance}
}
|
Keywords: |
|
Mastermind, Query Complexity, l_p Distance |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
17.09.2019 |
