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 f z,π (x) defined as More... »

PAGES

1-11

References to SciGraph publications

Book

TITLE

Space-Efficient Data Structures, Streams, and Algorithms

ISBN

978-3-642-40272-2
978-3-642-40273-9

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/1117", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Public Health and Health Services", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Aarhus University", 
          "id": "https://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", 
          "id": "https://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", 
          "id": "https://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": "Max Planck Institute for Informatics", 
          "id": "https://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"
          ], 
          "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": "Aarhus University", 
          "id": "https://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", 
          "id": "https://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"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0304-3975(01)00303-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001245016"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02579188", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004872612", 
          "https://doi.org/10.1007/bf02579188"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-13122-6_21", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007204202", 
          "https://doi.org/10.1007/978-3-642-13122-6_21"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-13122-6_21", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007204202", 
          "https://doi.org/10.1007/978-3-642-13122-6_21"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ipl.2009.02.021", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011379337"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(94)90181-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013684288"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-30347-0_36", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025082655", 
          "https://doi.org/10.1007/978-3-642-30347-0_36"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-35533-2_18", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037135703", 
          "https://doi.org/10.1007/978-3-642-35533-2_18"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-61332-3_138", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042770590", 
          "https://doi.org/10.1007/3-540-61332-3_138"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9781611973105.50", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088801657"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sp.2009.4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094814097"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "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 f z,\u03c0 (x) defined as", 
    "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", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-40272-2", 
        "978-3-642-40273-9"
      ], 
      "name": "Space-Efficient Data Structures, Streams, and Algorithms", 
      "type": "Book"
    }, 
    "name": "The Query Complexity of Finding a Hidden Permutation", 
    "pagination": "1-11", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-40273-9_1"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "65ef63ecdd8e68b2a0b447771a9a4bb51c6706a9ef5693390d489bee7fec0bf8"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1021394801"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "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": "2019-04-15T18:10", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8681_00000256.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/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.

156 TRIPLES      23 PREDICATES      37 URIs      20 LITERALS      8 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 N63149e5efdec4584b9a6e03a19c87a1a
4 schema:citation sg:pub.10.1007/3-540-61332-3_138
5 sg:pub.10.1007/978-3-642-13122-6_21
6 sg:pub.10.1007/978-3-642-30347-0_36
7 sg:pub.10.1007/978-3-642-35533-2_18
8 sg:pub.10.1007/bf02579188
9 https://doi.org/10.1016/0304-3975(94)90181-3
10 https://doi.org/10.1016/j.ipl.2009.02.021
11 https://doi.org/10.1016/s0304-3975(01)00303-6
12 https://doi.org/10.1109/sp.2009.4
13 https://doi.org/10.1137/1.9781611973105.50
14 schema:datePublished 2013
15 schema:datePublishedReg 2013-01-01
16 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 f z,π (x) defined as
17 schema:editor N2967d3c31da545d6bacd8729b934fa32
18 schema:genre chapter
19 schema:inLanguage en
20 schema:isAccessibleForFree true
21 schema:isPartOf N1b4511345b6b4f828618549d6a27f62e
22 schema:name The Query Complexity of Finding a Hidden Permutation
23 schema:pagination 1-11
24 schema:productId N144bee3bfd744c4489562f2cc294881f
25 N1e460ec095724166b8f3c60b8dcaf375
26 N236fc0f3b6874592870c6ff106bcf67d
27 schema:publisher Nb700105cffe34b89a075e525218e1200
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021394801
29 https://doi.org/10.1007/978-3-642-40273-9_1
30 schema:sdDatePublished 2019-04-15T18:10
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher Ne7bad03d2b2f44c8b4668c5c3cbad7ac
33 schema:url http://link.springer.com/10.1007/978-3-642-40273-9_1
34 sgo:license sg:explorer/license/
35 sgo:sdDataset chapters
36 rdf:type schema:Chapter
37 N01eae122ac704ed980b4e5f90d1683f8 rdf:first N430b2dc94b394cb8a0f2f9a52d740d60
38 rdf:rest N5cf2fc62b5124df0a9ae9d13442b0a67
39 N06387648ab5445b68f1dec2db9a4ba37 rdf:first sg:person.012173571625.60
40 rdf:rest N7e2e9e3e81bf4893bd74affec8fad9b1
41 N0666e0f0381740c9bb2ac332fe0d083b rdf:first sg:person.01327223002.89
42 rdf:rest N172345eaffea468a97fba2291faff32f
43 N144bee3bfd744c4489562f2cc294881f schema:name readcube_id
44 schema:value 65ef63ecdd8e68b2a0b447771a9a4bb51c6706a9ef5693390d489bee7fec0bf8
45 rdf:type schema:PropertyValue
46 N172345eaffea468a97fba2291faff32f rdf:first sg:person.010360414373.45
47 rdf:rest N06387648ab5445b68f1dec2db9a4ba37
48 N1b4511345b6b4f828618549d6a27f62e schema:isbn 978-3-642-40272-2
49 978-3-642-40273-9
50 schema:name Space-Efficient Data Structures, Streams, and Algorithms
51 rdf:type schema:Book
52 N1e460ec095724166b8f3c60b8dcaf375 schema:name doi
53 schema:value 10.1007/978-3-642-40273-9_1
54 rdf:type schema:PropertyValue
55 N236fc0f3b6874592870c6ff106bcf67d schema:name dimensions_id
56 schema:value pub.1021394801
57 rdf:type schema:PropertyValue
58 N2967d3c31da545d6bacd8729b934fa32 rdf:first Nd230ebf5c9ce4b41ab3957952ec7ba21
59 rdf:rest Nb86bc54bfab44f34890c0c8339993e33
60 N430b2dc94b394cb8a0f2f9a52d740d60 schema:familyName Raman
61 schema:givenName Venkatesh
62 rdf:type schema:Person
63 N5cf2fc62b5124df0a9ae9d13442b0a67 rdf:first N85eda65e285242629d8fecad2b4a98f9
64 rdf:rest rdf:nil
65 N63149e5efdec4584b9a6e03a19c87a1a rdf:first sg:person.010017520640.73
66 rdf:rest Nf90fa409dbb14610bec050f2232f6e48
67 N724c7481594d4edb9b8b25c556ac32f2 schema:familyName López-Ortiz
68 schema:givenName Alejandro
69 rdf:type schema:Person
70 N7e2e9e3e81bf4893bd74affec8fad9b1 rdf:first sg:person.011757371347.43
71 rdf:rest rdf:nil
72 N85eda65e285242629d8fecad2b4a98f9 schema:familyName Viola
73 schema:givenName Alfredo
74 rdf:type schema:Person
75 Nb700105cffe34b89a075e525218e1200 schema:location Berlin, Heidelberg
76 schema:name Springer Berlin Heidelberg
77 rdf:type schema:Organisation
78 Nb86bc54bfab44f34890c0c8339993e33 rdf:first N724c7481594d4edb9b8b25c556ac32f2
79 rdf:rest N01eae122ac704ed980b4e5f90d1683f8
80 Nd230ebf5c9ce4b41ab3957952ec7ba21 schema:familyName Brodnik
81 schema:givenName Andrej
82 rdf:type schema:Person
83 Ne7bad03d2b2f44c8b4668c5c3cbad7ac schema:name Springer Nature - SN SciGraph project
84 rdf:type schema:Organization
85 Nf90fa409dbb14610bec050f2232f6e48 rdf:first sg:person.012674600545.45
86 rdf:rest N0666e0f0381740c9bb2ac332fe0d083b
87 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
88 schema:name Medical and Health Sciences
89 rdf:type schema:DefinedTerm
90 anzsrc-for:1117 schema:inDefinedTermSet anzsrc-for:
91 schema:name Public Health and Health Services
92 rdf:type schema:DefinedTerm
93 sg:person.010017520640.73 schema:affiliation https://www.grid.ac/institutes/grid.7048.b
94 schema:familyName Afshani
95 schema:givenName Peyman
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010017520640.73
97 rdf:type schema:Person
98 sg:person.010360414373.45 schema:affiliation https://www.grid.ac/institutes/grid.419528.3
99 schema:familyName Doerr
100 schema:givenName Carola
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010360414373.45
102 rdf:type schema:Person
103 sg:person.011757371347.43 schema:affiliation https://www.grid.ac/institutes/grid.419528.3
104 schema:familyName Mehlhorn
105 schema:givenName Kurt
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
107 rdf:type schema:Person
108 sg:person.012173571625.60 schema:affiliation https://www.grid.ac/institutes/grid.7048.b
109 schema:familyName Larsen
110 schema:givenName Kasper Green
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012173571625.60
112 rdf:type schema:Person
113 sg:person.012674600545.45 schema:affiliation https://www.grid.ac/institutes/grid.417965.8
114 schema:familyName Agrawal
115 schema:givenName Manindra
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012674600545.45
117 rdf:type schema:Person
118 sg:person.01327223002.89 schema:affiliation https://www.grid.ac/institutes/grid.419528.3
119 schema:familyName Doerr
120 schema:givenName Benjamin
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01327223002.89
122 rdf:type schema:Person
123 sg:pub.10.1007/3-540-61332-3_138 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042770590
124 https://doi.org/10.1007/3-540-61332-3_138
125 rdf:type schema:CreativeWork
126 sg:pub.10.1007/978-3-642-13122-6_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007204202
127 https://doi.org/10.1007/978-3-642-13122-6_21
128 rdf:type schema:CreativeWork
129 sg:pub.10.1007/978-3-642-30347-0_36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025082655
130 https://doi.org/10.1007/978-3-642-30347-0_36
131 rdf:type schema:CreativeWork
132 sg:pub.10.1007/978-3-642-35533-2_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037135703
133 https://doi.org/10.1007/978-3-642-35533-2_18
134 rdf:type schema:CreativeWork
135 sg:pub.10.1007/bf02579188 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004872612
136 https://doi.org/10.1007/bf02579188
137 rdf:type schema:CreativeWork
138 https://doi.org/10.1016/0304-3975(94)90181-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013684288
139 rdf:type schema:CreativeWork
140 https://doi.org/10.1016/j.ipl.2009.02.021 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011379337
141 rdf:type schema:CreativeWork
142 https://doi.org/10.1016/s0304-3975(01)00303-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001245016
143 rdf:type schema:CreativeWork
144 https://doi.org/10.1109/sp.2009.4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094814097
145 rdf:type schema:CreativeWork
146 https://doi.org/10.1137/1.9781611973105.50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801657
147 rdf:type schema:CreativeWork
148 https://www.grid.ac/institutes/grid.417965.8 schema:alternateName Indian Institute of Technology Kanpur
149 schema:name Indian Institute of Technology Kanpur, India
150 rdf:type schema:Organization
151 https://www.grid.ac/institutes/grid.419528.3 schema:alternateName Max Planck Institute for Informatics
152 schema:name Max Planck Institute for Informatics, Saarbrücken, Germany
153 rdf:type schema:Organization
154 https://www.grid.ac/institutes/grid.7048.b schema:alternateName Aarhus University
155 schema:name MADALGO, Department of Computer Science, Aarhus University, Denmark
156 rdf:type schema:Organization
 




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


...