Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1997

AUTHORS

Alexander E. Andreev , Andrea E. F. Clementi , José D. P. Rolim

ABSTRACT

Our conditions refer to the worst-case circuit complexity of Boolean operators computable in time exponential in the input size. Such results are achieved by a new method that departs significantly from the usual known methods based on pseudo-random generators.

PAGES

177-187

References to SciGraph publications

  • 1986-06. Eigenvalues and expanders in COMBINATORICA
  • 1996. Hitting sets derandomize BPP in AUTOMATA, LANGUAGES AND PROGRAMMING
  • Book

    TITLE

    Automata, Languages and Programming

    ISBN

    978-3-540-63165-1
    978-3-540-69194-5

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-63165-8_175

    DOI

    http://dx.doi.org/10.1007/3-540-63165-8_175

    DIMENSIONS

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


    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", 
        "author": [
          {
            "affiliation": {
              "name": [
                "Dept. of Mathematics, University of Moscow, USSR"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Andreev", 
            "givenName": "Alexander E.", 
            "id": "sg:person.012322036405.59", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012322036405.59"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Dip. di Scienze dell'Informazione, University \u201cLa Sapienza\u201d of Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Clementi", 
            "givenName": "Andrea E. F.", 
            "id": "sg:person.011027660123.21", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011027660123.21"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Geneva", 
              "id": "https://www.grid.ac/institutes/grid.8591.5", 
              "name": [
                "Centre Universitaire d'Informatique, University of Geneva, CH"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Rolim", 
            "givenName": "Jos\u00e9 D. P.", 
            "id": "sg:person.013274060005.11", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013274060005.11"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-61440-0_142", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001553486", 
              "https://doi.org/10.1007/3-540-61440-0_142"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-0000(05)80043-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007093312"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02579166", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009922230", 
              "https://doi.org/10.1007/bf02579166"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02579166", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009922230", 
              "https://doi.org/10.1007/bf02579166"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/237814.237878", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035346448"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/28395.28410", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039385294"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0213053", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841787"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1982.45", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086226123"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1997.646115", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094073686"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1997", 
        "datePublishedReg": "1997-01-01", 
        "description": "Our conditions refer to the worst-case circuit complexity of Boolean operators computable in time exponential in the input size. Such results are achieved by a new method that departs significantly from the usual known methods based on pseudo-random generators.", 
        "editor": [
          {
            "familyName": "Degano", 
            "givenName": "Pierpaolo", 
            "type": "Person"
          }, 
          {
            "familyName": "Gorrieri", 
            "givenName": "Roberto", 
            "type": "Person"
          }, 
          {
            "familyName": "Marchetti-Spaccamela", 
            "givenName": "Alberto", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-63165-8_175", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-63165-1", 
            "978-3-540-69194-5"
          ], 
          "name": "Automata, Languages and Programming", 
          "type": "Book"
        }, 
        "name": "Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs", 
        "pagination": "177-187", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-63165-8_175"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "b14ca101d815fbefeb6e0cfdf2541bf002547340b489fc90e0b316addd5d0372"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1037219358"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-63165-8_175", 
          "https://app.dimensions.ai/details/publication/pub.1037219358"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T12:33", 
        "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_8663_00000266.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/3-540-63165-8_175"
      }
    ]
     

    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/3-540-63165-8_175'

    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/3-540-63165-8_175'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-63165-8_175'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-63165-8_175'


     

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

    111 TRIPLES      22 PREDICATES      33 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-63165-8_175 schema:author N80b68bf3383b4041bc0c7654f1d7b70c
    2 schema:citation sg:pub.10.1007/3-540-61440-0_142
    3 sg:pub.10.1007/bf02579166
    4 https://doi.org/10.1016/s0022-0000(05)80043-1
    5 https://doi.org/10.1109/sfcs.1982.45
    6 https://doi.org/10.1109/sfcs.1997.646115
    7 https://doi.org/10.1137/0213053
    8 https://doi.org/10.1145/237814.237878
    9 https://doi.org/10.1145/28395.28410
    10 schema:datePublished 1997
    11 schema:datePublishedReg 1997-01-01
    12 schema:description Our conditions refer to the worst-case circuit complexity of Boolean operators computable in time exponential in the input size. Such results are achieved by a new method that departs significantly from the usual known methods based on pseudo-random generators.
    13 schema:editor N7b7f9d69c2be42fda5ab8a25edc2a758
    14 schema:genre chapter
    15 schema:inLanguage en
    16 schema:isAccessibleForFree false
    17 schema:isPartOf N9afdfbd80b284dad839e3e44c3f9d013
    18 schema:name Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs
    19 schema:pagination 177-187
    20 schema:productId N3456a4bba9e942cd84b674b648015ecb
    21 N7fce53b0f40742438362216592bfec01
    22 N98417b3ec8b94b718b2e05df72e6f0f2
    23 schema:publisher Ncfdbd0a6262341bd83c5ed68b3061890
    24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037219358
    25 https://doi.org/10.1007/3-540-63165-8_175
    26 schema:sdDatePublished 2019-04-15T12:33
    27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    28 schema:sdPublisher Ne9c6fc59b55844948c97371140631bcd
    29 schema:url http://link.springer.com/10.1007/3-540-63165-8_175
    30 sgo:license sg:explorer/license/
    31 sgo:sdDataset chapters
    32 rdf:type schema:Chapter
    33 N08f49d2fb02b4f509fdb4d937e0f5be9 schema:familyName Marchetti-Spaccamela
    34 schema:givenName Alberto
    35 rdf:type schema:Person
    36 N3456a4bba9e942cd84b674b648015ecb schema:name dimensions_id
    37 schema:value pub.1037219358
    38 rdf:type schema:PropertyValue
    39 N4a55922b92a74c98a8587864a0215992 schema:familyName Gorrieri
    40 schema:givenName Roberto
    41 rdf:type schema:Person
    42 N6878aa38fdcc4839b9535021cf4f0c32 schema:name Dip. di Scienze dell'Informazione, University “La Sapienza” of Rome, Italy
    43 rdf:type schema:Organization
    44 N7b7f9d69c2be42fda5ab8a25edc2a758 rdf:first N8a1fb2100afe46e2919b80290a5215b0
    45 rdf:rest Nac05887a8562433daeadb66e67d1aca1
    46 N7fce53b0f40742438362216592bfec01 schema:name doi
    47 schema:value 10.1007/3-540-63165-8_175
    48 rdf:type schema:PropertyValue
    49 N80b68bf3383b4041bc0c7654f1d7b70c rdf:first sg:person.012322036405.59
    50 rdf:rest Nda9296591ee74ca4afb5c05f7583724e
    51 N81ea707ba6bc48ed98a0a6c020a03622 schema:name Dept. of Mathematics, University of Moscow, USSR
    52 rdf:type schema:Organization
    53 N8a1fb2100afe46e2919b80290a5215b0 schema:familyName Degano
    54 schema:givenName Pierpaolo
    55 rdf:type schema:Person
    56 N98417b3ec8b94b718b2e05df72e6f0f2 schema:name readcube_id
    57 schema:value b14ca101d815fbefeb6e0cfdf2541bf002547340b489fc90e0b316addd5d0372
    58 rdf:type schema:PropertyValue
    59 N9afdfbd80b284dad839e3e44c3f9d013 schema:isbn 978-3-540-63165-1
    60 978-3-540-69194-5
    61 schema:name Automata, Languages and Programming
    62 rdf:type schema:Book
    63 Nac05887a8562433daeadb66e67d1aca1 rdf:first N4a55922b92a74c98a8587864a0215992
    64 rdf:rest Nd6bd9876292a476a81b71f9120b4dad9
    65 Ncfdbd0a6262341bd83c5ed68b3061890 schema:location Berlin, Heidelberg
    66 schema:name Springer Berlin Heidelberg
    67 rdf:type schema:Organisation
    68 Nd6bd9876292a476a81b71f9120b4dad9 rdf:first N08f49d2fb02b4f509fdb4d937e0f5be9
    69 rdf:rest rdf:nil
    70 Nda9296591ee74ca4afb5c05f7583724e rdf:first sg:person.011027660123.21
    71 rdf:rest Ne81de5713f5047308aaa9f46cbf3353e
    72 Ne81de5713f5047308aaa9f46cbf3353e rdf:first sg:person.013274060005.11
    73 rdf:rest rdf:nil
    74 Ne9c6fc59b55844948c97371140631bcd schema:name Springer Nature - SN SciGraph project
    75 rdf:type schema:Organization
    76 sg:person.011027660123.21 schema:affiliation N6878aa38fdcc4839b9535021cf4f0c32
    77 schema:familyName Clementi
    78 schema:givenName Andrea E. F.
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011027660123.21
    80 rdf:type schema:Person
    81 sg:person.012322036405.59 schema:affiliation N81ea707ba6bc48ed98a0a6c020a03622
    82 schema:familyName Andreev
    83 schema:givenName Alexander E.
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012322036405.59
    85 rdf:type schema:Person
    86 sg:person.013274060005.11 schema:affiliation https://www.grid.ac/institutes/grid.8591.5
    87 schema:familyName Rolim
    88 schema:givenName José D. P.
    89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013274060005.11
    90 rdf:type schema:Person
    91 sg:pub.10.1007/3-540-61440-0_142 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001553486
    92 https://doi.org/10.1007/3-540-61440-0_142
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/bf02579166 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009922230
    95 https://doi.org/10.1007/bf02579166
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1016/s0022-0000(05)80043-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007093312
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1109/sfcs.1982.45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086226123
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1109/sfcs.1997.646115 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094073686
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1137/0213053 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841787
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1145/237814.237878 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035346448
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1145/28395.28410 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039385294
    108 rdf:type schema:CreativeWork
    109 https://www.grid.ac/institutes/grid.8591.5 schema:alternateName University of Geneva
    110 schema:name Centre Universitaire d'Informatique, University of Geneva, CH
    111 rdf:type schema:Organization
     




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


    ...