The Query Complexity of Finding a Hidden Permutation View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

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

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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ f_{z,\pi}(x):= \max \{ i \in[0..n]\mid \forall j \leq i: z_{\pi(j)} = x_{\pi(j)}\}\,;$$\end{document} 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 logn) and Θ(n loglogn), respectively. More... »

PAGES

1-11

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-40273-9_1

DOI

http://dx.doi.org/10.1007/978-3-642-40273-9_1

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1021394801


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/11", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Medical and Health Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1117", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Public Health and Health Services", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "MADALGO, Department of Computer Science, Aarhus University, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.7048.b", 
          "name": [
            "MADALGO, Department of Computer Science, Aarhus University, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Afshani", 
        "givenName": "Peyman", 
        "id": "sg:person.010017520640.73", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010017520640.73"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Indian Institute of Technology Kanpur, India", 
          "id": "http://www.grid.ac/institutes/grid.417965.8", 
          "name": [
            "Indian Institute of Technology Kanpur, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Agrawal", 
        "givenName": "Manindra", 
        "id": "sg:person.012674600545.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012674600545.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Doerr", 
        "givenName": "Benjamin", 
        "id": "sg:person.01327223002.89", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01327223002.89"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "LIAFA, Universit\u00e9 Paris Diderot - Paris 7, Paris, France", 
          "id": "http://www.grid.ac/institutes/grid.462842.e", 
          "name": [
            "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany", 
            "LIAFA, Universit\u00e9 Paris Diderot - Paris 7, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Doerr", 
        "givenName": "Carola", 
        "id": "sg:person.010360414373.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010360414373.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MADALGO, Department of Computer Science, Aarhus University, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.7048.b", 
          "name": [
            "MADALGO, Department of Computer Science, Aarhus University, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Larsen", 
        "givenName": "Kasper Green", 
        "id": "sg:person.012173571625.60", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012173571625.60"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehlhorn", 
        "givenName": "Kurt", 
        "id": "sg:person.011757371347.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "We study the query complexity of determining a hidden permutation. More specifically, we study the problem of learning a secret (z,\u03c0) consisting of a binary string z of length n and a permutation \u03c0 of [n]. The secret must be unveiled by asking queries x\u2009\u2208\u2009{0,1}n, and for each query asked, we are returned the score fz,\u03c0(x) defined as \n\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$ f_{z,\\pi}(x):= \\max \\{ i \\in[0..n]\\mid \\forall j \\leq i: z_{\\pi(j)} = x_{\\pi(j)}\\}\\,;$$\\end{document} i.e., the length of the longest common prefix of x and z with respect to \u03c0. 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 \u0398(n logn) and \u0398(n loglogn), respectively.", 
    "editor": [
      {
        "familyName": "Brodnik", 
        "givenName": "Andrej", 
        "type": "Person"
      }, 
      {
        "familyName": "L\u00f3pez-Ortiz", 
        "givenName": "Alejandro", 
        "type": "Person"
      }, 
      {
        "familyName": "Raman", 
        "givenName": "Venkatesh", 
        "type": "Person"
      }, 
      {
        "familyName": "Viola", 
        "givenName": "Alfredo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-40273-9_1", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-40272-2", 
        "978-3-642-40273-9"
      ], 
      "name": "Space-Efficient Data Structures, Streams, and Algorithms", 
      "type": "Book"
    }, 
    "keywords": [
      "query complexity", 
      "scores", 
      "number of queries", 
      "complexity", 
      "queries", 
      "longest common prefix", 
      "common prefix", 
      "number", 
      "permutations", 
      "secrets", 
      "length n", 
      "length", 
      "prefix", 
      "respect", 
      "goal", 
      "lower bounds", 
      "problem", 
      "permutation \u03c0", 
      "bounds", 
      "deterministic", 
      "string z", 
      "query x"
    ], 
    "name": "The Query Complexity of Finding a Hidden Permutation", 
    "pagination": "1-11", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1021394801"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-40273-9_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-40273-9_1", 
      "https://app.dimensions.ai/details/publication/pub.1021394801"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-09-02T16:18", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/chapter/chapter_72.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-40273-9_1"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-40273-9_1'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-40273-9_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-40273-9_1'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-40273-9_1'


 

This table displays all metadata directly associated to this object as RDF triples.

141 TRIPLES      22 PREDICATES      47 URIs      40 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-40273-9_1 schema:about anzsrc-for:11
2 anzsrc-for:1117
3 schema:author N93bd854894a7472ba94951812588d42a
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ f_{z,\pi}(x):= \max \{ i \in[0..n]\mid \forall j \leq i: z_{\pi(j)} = x_{\pi(j)}\}\,;$$\end{document} 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 logn) and Θ(n loglogn), respectively.
7 schema:editor N98bd3adc9bbb4055b4c4869c61348321
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Nc6e7eeb568dc4b039e49b416a2394ca9
11 schema:keywords bounds
12 common prefix
13 complexity
14 deterministic
15 goal
16 length
17 length n
18 longest common prefix
19 lower bounds
20 number
21 number of queries
22 permutation π
23 permutations
24 prefix
25 problem
26 queries
27 query complexity
28 query x
29 respect
30 scores
31 secrets
32 string z
33 schema:name The Query Complexity of Finding a Hidden Permutation
34 schema:pagination 1-11
35 schema:productId N3c43ad76e3164928a3778d2b05297e6f
36 Necd632afb6674b47849094fc2ffa3263
37 schema:publisher N81dfa46b523b44a3822ba23e5e2329af
38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021394801
39 https://doi.org/10.1007/978-3-642-40273-9_1
40 schema:sdDatePublished 2022-09-02T16:18
41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
42 schema:sdPublisher N8e423081926f42bdb6211bc43b534de2
43 schema:url https://doi.org/10.1007/978-3-642-40273-9_1
44 sgo:license sg:explorer/license/
45 sgo:sdDataset chapters
46 rdf:type schema:Chapter
47 N0583ad10daaf4835815fb95225a1ecf7 rdf:first sg:person.012674600545.45
48 rdf:rest N78fedf398e8347acadb94636d7abf719
49 N101161c9728c421cac62f2daa3ba0cce schema:familyName López-Ortiz
50 schema:givenName Alejandro
51 rdf:type schema:Person
52 N2c803b90a94a4c3d880e1977db509472 rdf:first Ne910c6c8e8634d7786c5e7ba8449fdc1
53 rdf:rest N57a67c2667784324a51a569399334e11
54 N35614e61fb4c44e39cbe1c904835dcc6 schema:familyName Brodnik
55 schema:givenName Andrej
56 rdf:type schema:Person
57 N3c43ad76e3164928a3778d2b05297e6f schema:name dimensions_id
58 schema:value pub.1021394801
59 rdf:type schema:PropertyValue
60 N52ca8df540364d27be1f89aafee9a934 rdf:first sg:person.012173571625.60
61 rdf:rest N72c2322048144f1db9a1a31e30d3c4d5
62 N57a67c2667784324a51a569399334e11 rdf:first Nf5c59669ef314214b922fa8640ab4a6b
63 rdf:rest rdf:nil
64 N72c2322048144f1db9a1a31e30d3c4d5 rdf:first sg:person.011757371347.43
65 rdf:rest rdf:nil
66 N78fedf398e8347acadb94636d7abf719 rdf:first sg:person.01327223002.89
67 rdf:rest Nd84d5357164f4ece924e220736f62231
68 N81dfa46b523b44a3822ba23e5e2329af schema:name Springer Nature
69 rdf:type schema:Organisation
70 N8e423081926f42bdb6211bc43b534de2 schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 N93bd854894a7472ba94951812588d42a rdf:first sg:person.010017520640.73
73 rdf:rest N0583ad10daaf4835815fb95225a1ecf7
74 N98bd3adc9bbb4055b4c4869c61348321 rdf:first N35614e61fb4c44e39cbe1c904835dcc6
75 rdf:rest Ne2efb3becfc54157bf998309efc22235
76 Nc6e7eeb568dc4b039e49b416a2394ca9 schema:isbn 978-3-642-40272-2
77 978-3-642-40273-9
78 schema:name Space-Efficient Data Structures, Streams, and Algorithms
79 rdf:type schema:Book
80 Nd84d5357164f4ece924e220736f62231 rdf:first sg:person.010360414373.45
81 rdf:rest N52ca8df540364d27be1f89aafee9a934
82 Ne2efb3becfc54157bf998309efc22235 rdf:first N101161c9728c421cac62f2daa3ba0cce
83 rdf:rest N2c803b90a94a4c3d880e1977db509472
84 Ne910c6c8e8634d7786c5e7ba8449fdc1 schema:familyName Raman
85 schema:givenName Venkatesh
86 rdf:type schema:Person
87 Necd632afb6674b47849094fc2ffa3263 schema:name doi
88 schema:value 10.1007/978-3-642-40273-9_1
89 rdf:type schema:PropertyValue
90 Nf5c59669ef314214b922fa8640ab4a6b schema:familyName Viola
91 schema:givenName Alfredo
92 rdf:type schema:Person
93 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
94 schema:name Medical and Health Sciences
95 rdf:type schema:DefinedTerm
96 anzsrc-for:1117 schema:inDefinedTermSet anzsrc-for:
97 schema:name Public Health and Health Services
98 rdf:type schema:DefinedTerm
99 sg:person.010017520640.73 schema:affiliation grid-institutes:grid.7048.b
100 schema:familyName Afshani
101 schema:givenName Peyman
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010017520640.73
103 rdf:type schema:Person
104 sg:person.010360414373.45 schema:affiliation grid-institutes:grid.462842.e
105 schema:familyName Doerr
106 schema:givenName Carola
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010360414373.45
108 rdf:type schema:Person
109 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
110 schema:familyName Mehlhorn
111 schema:givenName Kurt
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
113 rdf:type schema:Person
114 sg:person.012173571625.60 schema:affiliation grid-institutes:grid.7048.b
115 schema:familyName Larsen
116 schema:givenName Kasper Green
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012173571625.60
118 rdf:type schema:Person
119 sg:person.012674600545.45 schema:affiliation grid-institutes:grid.417965.8
120 schema:familyName Agrawal
121 schema:givenName Manindra
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012674600545.45
123 rdf:type schema:Person
124 sg:person.01327223002.89 schema:affiliation grid-institutes:grid.419528.3
125 schema:familyName Doerr
126 schema:givenName Benjamin
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01327223002.89
128 rdf:type schema:Person
129 grid-institutes:grid.417965.8 schema:alternateName Indian Institute of Technology Kanpur, India
130 schema:name Indian Institute of Technology Kanpur, India
131 rdf:type schema:Organization
132 grid-institutes:grid.419528.3 schema:alternateName Max Planck Institute for Informatics, Saarbrücken, Germany
133 schema:name Max Planck Institute for Informatics, Saarbrücken, Germany
134 rdf:type schema:Organization
135 grid-institutes:grid.462842.e schema:alternateName LIAFA, Université Paris Diderot - Paris 7, Paris, France
136 schema:name LIAFA, Université Paris Diderot - Paris 7, Paris, France
137 Max Planck Institute for Informatics, Saarbrücken, Germany
138 rdf:type schema:Organization
139 grid-institutes:grid.7048.b schema:alternateName MADALGO, Department of Computer Science, Aarhus University, Denmark
140 schema:name MADALGO, Department of Computer Science, Aarhus University, Denmark
141 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...