OneMax in Black-Box Models with Several Restrictions View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2017-06

AUTHORS

Carola Doerr, Johannes Lengler

ABSTRACT

Black-box complexity studies lower bounds for the efficiency of general-purpose black-box optimization algorithms such as evolutionary algorithms and other search heuristics. Different models exist, each one being designed to analyze a different aspect of typical heuristics such as the memory size or the variation operators in use. While most of the previous works focus on one particular such aspect, we consider in this work how the combination of several algorithmic restrictions influence the black-box complexity of a problem. Our testbed are so-called OneMax functions which require to minimize the Hamming distance to an unknown target string z∈{0,1}n. We analyze in particular the combined memory-restricted ranking-based black-box complexity of OneMax for different memory sizes. While its isolated (1+1) memory-restricted as well as its ranking-based black-box complexity for bit strings of length n is only of order n/logn, the combined model does not allow for algorithms being faster than linear in n, as can easily be seen by standard information-theoretic considerations. Our main result is a matching upper bound. That is, we show that the (1+1) memory-restricted ranking-based black-box complexity of OneMax is linear. We also analyze its black-box complexity for memory sizes other than (1+1). Moreover, we show that these results apply to the (Monte Carlo) complexity of OneMax in the recently introduced elitist model [Doerr/Lengler GECCO 2015] that combines the above-mentioned memory-restrictions and ranking-based decisions with an enforced usage of truncation selection. Finally, we also provide improved lower bounds for the complexity of OneMax in the regarded models. More... »

PAGES

610-640

References to SciGraph publications

  • 2012-12. Black-Box Search by Unbiased Variation in ALGORITHMICA
  • 2014-03. Ranking-Based Black-Box Complexity in ALGORITHMICA
  • 2006-07. Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization in THEORY OF COMPUTING SYSTEMS
  • 2006. General Lower Bounds for Evolutionary Algorithms in PARALLEL PROBLEM SOLVING FROM NATURE - PPSN IX
  • 2002-10-04. On the Analysis of Dynamic Restart Strategies for Evolutionary Algorithms in PARALLEL PROBLEM SOLVING FROM NATURE — PPSN VII
  • 2014-11. Playing Mastermind with Constant-Size Memory in THEORY OF COMPUTING SYSTEMS
  • 2011-03. Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation in ALGORITHMICA
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00453-016-0168-1

    DOI

    http://dx.doi.org/10.1007/s00453-016-0168-1

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Sorbonne University", 
              "id": "https://www.grid.ac/institutes/grid.462844.8", 
              "name": [
                "CNRS and Sorbonne Universit\u00e9s, UPMC Univ Paris 06, LIP6 UMR 7606, 4 place Jussieu, 75005, 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": "Swiss Federal Institute of Technology in Zurich", 
              "id": "https://www.grid.ac/institutes/grid.5801.c", 
              "name": [
                "Institute for Theoretical Computer Science, ETH Z\u00fcrich, Z\u00fcrich, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lengler", 
            "givenName": "Johannes", 
            "id": "sg:person.01104137534.89", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01104137534.89"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-45712-7_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001610718", 
              "https://doi.org/10.1007/3-540-45712-7_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45712-7_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001610718", 
              "https://doi.org/10.1007/3-540-45712-7_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1967654.1967669", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006048249"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1830483.1830747", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006054071"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2014.11.028", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008296423"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-010-9387-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011120996", 
              "https://doi.org/10.1007/s00453-010-9387-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1527125.1527135", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020839539"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2739480.2754678", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022158020"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2013.05.004", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036943015"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-004-1177-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040195428", 
              "https://doi.org/10.1007/s00224-004-1177-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-012-9616-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045973415", 
              "https://doi.org/10.1007/s00453-012-9616-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-012-9684-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048445835", 
              "https://doi.org/10.1007/s00453-012-9684-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11844297_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049657725", 
              "https://doi.org/10.1007/11844297_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11844297_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049657725", 
              "https://doi.org/10.1007/11844297_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-012-9438-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051006109", 
              "https://doi.org/10.1007/s00224-012-9438-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2598394.2605352", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053145784"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2739480.2754654", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053304664"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/2312725", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1069880361"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1977.24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086173273"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/9789814282673_0001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1088792900"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9780511814075", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098701235"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2017-06", 
        "datePublishedReg": "2017-06-01", 
        "description": "Black-box complexity studies lower bounds for the efficiency of general-purpose black-box optimization algorithms such as evolutionary algorithms and other search heuristics. Different models exist, each one being designed to analyze a different aspect of typical heuristics such as the memory size or the variation operators in use. While most of the previous works focus on one particular such aspect, we consider in this work how the combination of several algorithmic restrictions influence the black-box complexity of a problem. Our testbed are so-called OneMax functions which require to minimize the Hamming distance to an unknown target string z\u2208{0,1}n. We analyze in particular the combined memory-restricted ranking-based black-box complexity of OneMax for different memory sizes. While its isolated (1+1) memory-restricted as well as its ranking-based black-box complexity for bit strings of length n is only of order n/logn, the combined model does not allow for algorithms being faster than linear in n, as can easily be seen by standard information-theoretic considerations. Our main result is a matching upper bound. That is, we show that the (1+1) memory-restricted ranking-based black-box complexity of OneMax is linear. We also analyze its black-box complexity for memory sizes other than (1+1). Moreover, we show that these results apply to the (Monte Carlo) complexity of OneMax in the recently introduced elitist model [Doerr/Lengler GECCO 2015] that combines the above-mentioned memory-restrictions and ranking-based decisions with an enforced usage of truncation selection. Finally, we also provide improved lower bounds for the complexity of OneMax in the regarded models.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00453-016-0168-1", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "78"
          }
        ], 
        "name": "OneMax in Black-Box Models with Several Restrictions", 
        "pagination": "610-640", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "3ba8917e4686c2aaa18ff55d4ef4d06a359a8db8298a433bcd90376501ae7923"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00453-016-0168-1"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1012522190"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00453-016-0168-1", 
          "https://app.dimensions.ai/details/publication/pub.1012522190"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T15:12", 
        "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_00000583.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2Fs00453-016-0168-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/s00453-016-0168-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/s00453-016-0168-1'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-016-0168-1'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-016-0168-1'


     

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

    135 TRIPLES      21 PREDICATES      46 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00453-016-0168-1 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N0682967a83504500abd01cf87c44e61d
    4 schema:citation sg:pub.10.1007/11844297_3
    5 sg:pub.10.1007/3-540-45712-7_4
    6 sg:pub.10.1007/s00224-004-1177-z
    7 sg:pub.10.1007/s00224-012-9438-8
    8 sg:pub.10.1007/s00453-010-9387-z
    9 sg:pub.10.1007/s00453-012-9616-8
    10 sg:pub.10.1007/s00453-012-9684-9
    11 https://doi.org/10.1016/j.tcs.2013.05.004
    12 https://doi.org/10.1016/j.tcs.2014.11.028
    13 https://doi.org/10.1017/cbo9780511814075
    14 https://doi.org/10.1109/sfcs.1977.24
    15 https://doi.org/10.1142/9789814282673_0001
    16 https://doi.org/10.1145/1527125.1527135
    17 https://doi.org/10.1145/1830483.1830747
    18 https://doi.org/10.1145/1967654.1967669
    19 https://doi.org/10.1145/2598394.2605352
    20 https://doi.org/10.1145/2739480.2754654
    21 https://doi.org/10.1145/2739480.2754678
    22 https://doi.org/10.2307/2312725
    23 schema:datePublished 2017-06
    24 schema:datePublishedReg 2017-06-01
    25 schema:description Black-box complexity studies lower bounds for the efficiency of general-purpose black-box optimization algorithms such as evolutionary algorithms and other search heuristics. Different models exist, each one being designed to analyze a different aspect of typical heuristics such as the memory size or the variation operators in use. While most of the previous works focus on one particular such aspect, we consider in this work how the combination of several algorithmic restrictions influence the black-box complexity of a problem. Our testbed are so-called OneMax functions which require to minimize the Hamming distance to an unknown target string z∈{0,1}n. We analyze in particular the combined memory-restricted ranking-based black-box complexity of OneMax for different memory sizes. While its isolated (1+1) memory-restricted as well as its ranking-based black-box complexity for bit strings of length n is only of order n/logn, the combined model does not allow for algorithms being faster than linear in n, as can easily be seen by standard information-theoretic considerations. Our main result is a matching upper bound. That is, we show that the (1+1) memory-restricted ranking-based black-box complexity of OneMax is linear. We also analyze its black-box complexity for memory sizes other than (1+1). Moreover, we show that these results apply to the (Monte Carlo) complexity of OneMax in the recently introduced elitist model [Doerr/Lengler GECCO 2015] that combines the above-mentioned memory-restrictions and ranking-based decisions with an enforced usage of truncation selection. Finally, we also provide improved lower bounds for the complexity of OneMax in the regarded models.
    26 schema:genre research_article
    27 schema:inLanguage en
    28 schema:isAccessibleForFree true
    29 schema:isPartOf N0a4b987d8308462bb489f1e8226f5ff6
    30 N4cfa23fea5984e11b7ff527201d58d28
    31 sg:journal.1047644
    32 schema:name OneMax in Black-Box Models with Several Restrictions
    33 schema:pagination 610-640
    34 schema:productId N0d3671de809e412c8490b4af922a0250
    35 N98e43e900c244f7b868c5ba38bf7dfab
    36 Nd3155ee2d1ce4ffc9e1f25f5057ab07f
    37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012522190
    38 https://doi.org/10.1007/s00453-016-0168-1
    39 schema:sdDatePublished 2019-04-10T15:12
    40 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    41 schema:sdPublisher N236965b1bc3948cf9b118e9cf5703f71
    42 schema:url http://link.springer.com/10.1007%2Fs00453-016-0168-1
    43 sgo:license sg:explorer/license/
    44 sgo:sdDataset articles
    45 rdf:type schema:ScholarlyArticle
    46 N0682967a83504500abd01cf87c44e61d rdf:first sg:person.010360414373.45
    47 rdf:rest N94ffc787a42b435f9ee09e2610e23fe5
    48 N0a4b987d8308462bb489f1e8226f5ff6 schema:volumeNumber 78
    49 rdf:type schema:PublicationVolume
    50 N0d3671de809e412c8490b4af922a0250 schema:name doi
    51 schema:value 10.1007/s00453-016-0168-1
    52 rdf:type schema:PropertyValue
    53 N236965b1bc3948cf9b118e9cf5703f71 schema:name Springer Nature - SN SciGraph project
    54 rdf:type schema:Organization
    55 N4cfa23fea5984e11b7ff527201d58d28 schema:issueNumber 2
    56 rdf:type schema:PublicationIssue
    57 N94ffc787a42b435f9ee09e2610e23fe5 rdf:first sg:person.01104137534.89
    58 rdf:rest rdf:nil
    59 N98e43e900c244f7b868c5ba38bf7dfab schema:name dimensions_id
    60 schema:value pub.1012522190
    61 rdf:type schema:PropertyValue
    62 Nd3155ee2d1ce4ffc9e1f25f5057ab07f schema:name readcube_id
    63 schema:value 3ba8917e4686c2aaa18ff55d4ef4d06a359a8db8298a433bcd90376501ae7923
    64 rdf:type schema:PropertyValue
    65 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Information and Computing Sciences
    67 rdf:type schema:DefinedTerm
    68 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Computation Theory and Mathematics
    70 rdf:type schema:DefinedTerm
    71 sg:journal.1047644 schema:issn 0178-4617
    72 1432-0541
    73 schema:name Algorithmica
    74 rdf:type schema:Periodical
    75 sg:person.010360414373.45 schema:affiliation https://www.grid.ac/institutes/grid.462844.8
    76 schema:familyName Doerr
    77 schema:givenName Carola
    78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010360414373.45
    79 rdf:type schema:Person
    80 sg:person.01104137534.89 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
    81 schema:familyName Lengler
    82 schema:givenName Johannes
    83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01104137534.89
    84 rdf:type schema:Person
    85 sg:pub.10.1007/11844297_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049657725
    86 https://doi.org/10.1007/11844297_3
    87 rdf:type schema:CreativeWork
    88 sg:pub.10.1007/3-540-45712-7_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001610718
    89 https://doi.org/10.1007/3-540-45712-7_4
    90 rdf:type schema:CreativeWork
    91 sg:pub.10.1007/s00224-004-1177-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1040195428
    92 https://doi.org/10.1007/s00224-004-1177-z
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/s00224-012-9438-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051006109
    95 https://doi.org/10.1007/s00224-012-9438-8
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/s00453-010-9387-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1011120996
    98 https://doi.org/10.1007/s00453-010-9387-z
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/s00453-012-9616-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045973415
    101 https://doi.org/10.1007/s00453-012-9616-8
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1007/s00453-012-9684-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048445835
    104 https://doi.org/10.1007/s00453-012-9684-9
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1016/j.tcs.2013.05.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036943015
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1016/j.tcs.2014.11.028 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008296423
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1017/cbo9780511814075 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098701235
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1109/sfcs.1977.24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086173273
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1142/9789814282673_0001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088792900
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1145/1527125.1527135 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020839539
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1145/1830483.1830747 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006054071
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1145/1967654.1967669 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006048249
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1145/2598394.2605352 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053145784
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1145/2739480.2754654 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053304664
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1145/2739480.2754678 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022158020
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.2307/2312725 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069880361
    129 rdf:type schema:CreativeWork
    130 https://www.grid.ac/institutes/grid.462844.8 schema:alternateName Sorbonne University
    131 schema:name CNRS and Sorbonne Universités, UPMC Univ Paris 06, LIP6 UMR 7606, 4 place Jussieu, 75005, Paris, France
    132 rdf:type schema:Organization
    133 https://www.grid.ac/institutes/grid.5801.c schema:alternateName Swiss Federal Institute of Technology in Zurich
    134 schema:name Institute for Theoretical Computer Science, ETH Zürich, Zürich, Switzerland
    135 rdf:type schema:Organization
     




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


    ...