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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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}ⁿ, 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.

Original language	English
Title of host publication	Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday
Publisher	Springer Verlag
Pages	1-11
Number of pages	11
ISBN (Print)	9783642402722
DOIs	https://doi.org/10.1007/978-3-642-40273-9_1
Publication status	Published - 1 Jan 2013
Externally published	Yes
Event	Conference on Space-Efficient Data Structures, Streams, and Algorithms - Waterloo, ON, Canada Duration: 15 Aug 2013 → 16 Aug 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8066 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Conference on Space-Efficient Data Structures, Streams, and Algorithms
Country/Territory	Canada
City	Waterloo, ON
Period	15/08/13 → 16/08/13

Access to Document

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

Cite this

Afshani, P., Agrawal, M., Doerr, B., Doerr, C., Larsen, K. G., & Mehlhorn, K. (2013). The query complexity of finding a hidden permutation. In Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday (pp. 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. pp. 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. in 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, pp. 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).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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. In 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

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this