From Logarithmic Advice to Single-Bit Advice View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

Oded Goldreich , Madhu Sudan , Luca Trevisan

ABSTRACT

Building on Barak’s work (Random’02), Fortnow and Santhanam (FOCS’04) proved a time hierarchy for probabilistic machines with one bit of advice. Their argument is based on an implicit translation technique, which allow to translate separation results for short (say logarithmic) advice (as shown by Barak) into separations for a single-bit advice. In this note, we make this technique explicit, by introducing an adequate translation lemma. More... »

PAGES

109-113

Book

TITLE

Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation

ISBN

978-3-642-22669-4
978-3-642-22670-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-22670-0_13

DOI

http://dx.doi.org/10.1007/978-3-642-22670-0_13

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "familyName": "Goldreich", 
        "givenName": "Oded", 
        "id": "sg:person.012050724555.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012050724555.27"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Sudan", 
        "givenName": "Madhu", 
        "id": "sg:person.014663420265.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Trevisan", 
        "givenName": "Luca", 
        "id": "sg:person.015761757701.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015761757701.03"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "Building on Barak\u2019s work (Random\u201902), Fortnow and Santhanam (FOCS\u201904) proved a time hierarchy for probabilistic machines with one bit of advice. Their argument is based on an implicit translation technique, which allow to translate separation results for short (say logarithmic) advice (as shown by Barak) into separations for a single-bit advice. In this note, we make this technique explicit, by introducing an adequate translation lemma.", 
    "editor": [
      {
        "familyName": "Goldreich", 
        "givenName": "Oded", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-22670-0_13", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-22669-4", 
        "978-3-642-22670-0"
      ], 
      "name": "Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "probabilistic machine", 
      "bits of advice", 
      "advice", 
      "short advice", 
      "time hierarchy", 
      "translation techniques", 
      "work", 
      "Fortnow", 
      "Santhanam", 
      "hierarchy", 
      "machine", 
      "bits", 
      "technique", 
      "separation results", 
      "results", 
      "note", 
      "lemma", 
      "argument", 
      "separation", 
      "Barak\u2019s work", 
      "implicit translation technique", 
      "single-bit advice", 
      "adequate translation lemma", 
      "translation lemma", 
      "Logarithmic Advice"
    ], 
    "name": "From Logarithmic Advice to Single-Bit Advice", 
    "pagination": "109-113", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1053046468"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-22670-0_13"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-22670-0_13", 
      "https://app.dimensions.ai/details/publication/pub.1053046468"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:28", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_80.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-22670-0_13"
  }
]
 

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-22670-0_13'

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-22670-0_13'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22670-0_13'

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-22670-0_13'


 

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

93 TRIPLES      23 PREDICATES      51 URIs      44 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-22670-0_13 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Na115cdf70b5a425bab19bedbdfa304c8
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description Building on Barak’s work (Random’02), Fortnow and Santhanam (FOCS’04) proved a time hierarchy for probabilistic machines with one bit of advice. Their argument is based on an implicit translation technique, which allow to translate separation results for short (say logarithmic) advice (as shown by Barak) into separations for a single-bit advice. In this note, we make this technique explicit, by introducing an adequate translation lemma.
7 schema:editor Nfbd45036227d4f628d9489395a013e66
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nec399325137640628d12a904e9156058
12 schema:keywords Barak’s work
13 Fortnow
14 Logarithmic Advice
15 Santhanam
16 adequate translation lemma
17 advice
18 argument
19 bits
20 bits of advice
21 hierarchy
22 implicit translation technique
23 lemma
24 machine
25 note
26 probabilistic machine
27 results
28 separation
29 separation results
30 short advice
31 single-bit advice
32 technique
33 time hierarchy
34 translation lemma
35 translation techniques
36 work
37 schema:name From Logarithmic Advice to Single-Bit Advice
38 schema:pagination 109-113
39 schema:productId N3cb150bec61b462a864bdc48b4d54e70
40 N9a25fea29a7f45588ed52aa3a101fc9e
41 schema:publisher N9b3aaf20f7194c6e9c814d424a586eba
42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053046468
43 https://doi.org/10.1007/978-3-642-22670-0_13
44 schema:sdDatePublished 2022-01-01T19:28
45 schema:sdLicense https://scigraph.springernature.com/explorer/license/
46 schema:sdPublisher N7f09cecda66745088e89c3a71256170c
47 schema:url https://doi.org/10.1007/978-3-642-22670-0_13
48 sgo:license sg:explorer/license/
49 sgo:sdDataset chapters
50 rdf:type schema:Chapter
51 N3cb150bec61b462a864bdc48b4d54e70 schema:name doi
52 schema:value 10.1007/978-3-642-22670-0_13
53 rdf:type schema:PropertyValue
54 N7f09cecda66745088e89c3a71256170c schema:name Springer Nature - SN SciGraph project
55 rdf:type schema:Organization
56 N916c5278857642e188f9c7134523a35c rdf:first sg:person.015761757701.03
57 rdf:rest rdf:nil
58 N9a25fea29a7f45588ed52aa3a101fc9e schema:name dimensions_id
59 schema:value pub.1053046468
60 rdf:type schema:PropertyValue
61 N9b3aaf20f7194c6e9c814d424a586eba schema:name Springer Nature
62 rdf:type schema:Organisation
63 Na115cdf70b5a425bab19bedbdfa304c8 rdf:first sg:person.012050724555.27
64 rdf:rest Nc349c5b956234de0b7b8add57f4b9d76
65 Na6532542f68446e585359cc98823030d schema:familyName Goldreich
66 schema:givenName Oded
67 rdf:type schema:Person
68 Nc349c5b956234de0b7b8add57f4b9d76 rdf:first sg:person.014663420265.17
69 rdf:rest N916c5278857642e188f9c7134523a35c
70 Nec399325137640628d12a904e9156058 schema:isbn 978-3-642-22669-4
71 978-3-642-22670-0
72 schema:name Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation
73 rdf:type schema:Book
74 Nfbd45036227d4f628d9489395a013e66 rdf:first Na6532542f68446e585359cc98823030d
75 rdf:rest rdf:nil
76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
77 schema:name Information and Computing Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
80 schema:name Artificial Intelligence and Image Processing
81 rdf:type schema:DefinedTerm
82 sg:person.012050724555.27 schema:familyName Goldreich
83 schema:givenName Oded
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012050724555.27
85 rdf:type schema:Person
86 sg:person.014663420265.17 schema:familyName Sudan
87 schema:givenName Madhu
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
89 rdf:type schema:Person
90 sg:person.015761757701.03 schema:familyName Trevisan
91 schema:givenName Luca
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015761757701.03
93 rdf:type schema:Person
 




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


...