The query complexity of finding a hidden permutation

Peyman Afshani; Manindra Agrawal; Benjamin Doerr; Carola Doerr; Kasper Green Larsen; Kurt Mehlhorn

doi:10.1007/978-3-642-40273-9_1

The query complexity of finding a hidden permutation

Peyman Afshani
, Manindra Agrawal
, Benjamin Doerr
, Carola Doerr
, Kasper Green Larsen
, Kurt Mehlhorn

Aarhus University
Indian Institute of Technology Kanpur
Max-Planck-Institut fur Informatik
Laboratoire de Probabilités et Modèles Aléatoires

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

Résumé

We study the query complexity of determining a hidden permutation. More specifically, we study the problem of learning a secret (z, π) consisting of a binary string z of length n and a permutation π of [n]. The secret must be unveiled by asking queries x ∈ {0, 1}ⁿ, and for each query asked, we are returned the score f_z,π (x) defined as f _z,π (x) := max{i ∈ [0..n] | ∀j ≤ i : z _{π (j)} = x_{π (j)}} ; i.e., the length of the longest common prefix of x and z with respect to π. The goal is to minimize the number of queries asked. We prove matching upper and lower bounds for the deterministic and randomized query complexity of Θ (n log n) and Θ (n log log n), respectively.

langue originale	Anglais
titre	Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday
Editeur	Springer Verlag
Pages	1-11
Nombre de pages	11
ISBN (imprimé)	9783642402722
Les DOIs	https://doi.org/10.1007/978-3-642-40273-9_1
état	Publié - 1 janv. 2013
Modification externe	Oui
Evénement	Conference on Space-Efficient Data Structures, Streams, and Algorithms - Waterloo, ON, Canada Durée: 15 août 2013 → 16 août 2013

Série de publications

Nom	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8066 LNCS
ISSN (imprimé)	0302-9743
ISSN (Electronique)	1611-3349

Une conférence

Une conférence	Conference on Space-Efficient Data Structures, Streams, and Algorithms
Pays/Territoire	Canada
La ville	Waterloo, ON
période	15/08/13 → 16/08/13

Accès au document

10.1007/978-3-642-40273-9_1

Contient cette citation

Afshani, P., Agrawal, M., Doerr, B., Doerr, C., Larsen, K. G., & Mehlhorn, K. (2013). The query complexity of finding a hidden permutation. Dans Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday (p. 1-11). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol 8066 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-40273-9_1

Afshani, Peyman ; Agrawal, Manindra ; Doerr, Benjamin et al. / The query complexity of finding a hidden permutation. Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday. Springer Verlag, 2013. p. 1-11 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7202d55e79ff428cbd3800a6d631ac73,

title = "The query complexity of finding a hidden permutation",

abstract = "We study the query complexity of determining a hidden permutation. More specifically, we study the problem of learning a secret (z, π) consisting of a binary string z of length n and a permutation π of [n]. The secret must be unveiled by asking queries x ∈ \{0, 1\}n, and for each query asked, we are returned the score fz,π (x) defined as f z,π (x) := max\{i ∈ [0..n] | ∀j ≤ i : z π (j) = xπ (j)\} ; i.e., the length of the longest common prefix of x and z with respect to π. The goal is to minimize the number of queries asked. We prove matching upper and lower bounds for the deterministic and randomized query complexity of Θ (n log n) and Θ (n log log n), respectively.",

author = "Peyman Afshani and Manindra Agrawal and Benjamin Doerr and Carola Doerr and Larsen, \{Kasper Green\} and Kurt Mehlhorn",

year = "2013",

month = jan,

day = "1",

doi = "10.1007/978-3-642-40273-9\_1",

language = "English",

isbn = "9783642402722",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "1--11",

booktitle = "Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday",

note = "Conference on Space-Efficient Data Structures, Streams, and Algorithms ; Conference date: 15-08-2013 Through 16-08-2013",

}

Afshani, P, Agrawal, M, Doerr, B, Doerr, C, Larsen, KG & Mehlhorn, K 2013, The query complexity of finding a hidden permutation. Dans Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), VOL. 8066 LNCS, Springer Verlag, p. 1-11, Conference on Space-Efficient Data Structures, Streams, and Algorithms, Waterloo, ON, Canada, 15/08/13. https://doi.org/10.1007/978-3-642-40273-9_1

The query complexity of finding a hidden permutation. / Afshani, Peyman; Agrawal, Manindra; Doerr, Benjamin et al.
Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday. Springer Verlag, 2013. p. 1-11 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol 8066 LNCS).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

TY - GEN

T1 - The query complexity of finding a hidden permutation

AU - Afshani, Peyman

AU - Agrawal, Manindra

AU - Doerr, Benjamin

AU - Doerr, Carola

AU - Larsen, Kasper Green

AU - Mehlhorn, Kurt

PY - 2013/1/1

Y1 - 2013/1/1

N2 - We study the query complexity of determining a hidden permutation. More specifically, we study the problem of learning a secret (z, π) consisting of a binary string z of length n and a permutation π of [n]. The secret must be unveiled by asking queries x ∈ {0, 1}n, and for each query asked, we are returned the score fz,π (x) defined as f z,π (x) := max{i ∈ [0..n] | ∀j ≤ i : z π (j) = xπ (j)} ; i.e., the length of the longest common prefix of x and z with respect to π. The goal is to minimize the number of queries asked. We prove matching upper and lower bounds for the deterministic and randomized query complexity of Θ (n log n) and Θ (n log log n), respectively.

AB - We study the query complexity of determining a hidden permutation. More specifically, we study the problem of learning a secret (z, π) consisting of a binary string z of length n and a permutation π of [n]. The secret must be unveiled by asking queries x ∈ {0, 1}n, and for each query asked, we are returned the score fz,π (x) defined as f z,π (x) := max{i ∈ [0..n] | ∀j ≤ i : z π (j) = xπ (j)} ; i.e., the length of the longest common prefix of x and z with respect to π. The goal is to minimize the number of queries asked. We prove matching upper and lower bounds for the deterministic and randomized query complexity of Θ (n log n) and Θ (n log log n), respectively.

U2 - 10.1007/978-3-642-40273-9_1

DO - 10.1007/978-3-642-40273-9_1

M3 - Conference contribution

AN - SCOPUS:84894189312

SN - 9783642402722

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 11

BT - Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday

PB - Springer Verlag

T2 - Conference on Space-Efficient Data Structures, Streams, and Algorithms

Y2 - 15 August 2013 through 16 August 2013

ER -

Afshani P, Agrawal M, Doerr B, Doerr C, Larsen KG, Mehlhorn K. The query complexity of finding a hidden permutation. Dans Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday. Springer Verlag. 2013. p. 1-11. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-40273-9_1

The query complexity of finding a hidden permutation

Résumé

Série de publications

Une conférence

Accès au document

Empreinte digitale

Contient cette citation