Simple dynamics for plurality consensus View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2017-08

AUTHORS

Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, Luca Trevisan

ABSTRACT

We study a plurality-consensus process in which each of n anonymous agents of a communication network initially supports a color chosen from the set [k]. Then, in every round, each agent can revise his color according to the colors currently held by a random sample of his neighbors. It is assumed that the initial color configuration exhibits a sufficiently large biass towards a fixed plurality color, that is, the number of nodes supporting the plurality color exceeds the number of nodes supporting any other color by s additional nodes. The goal is having the process to converge to the stable configuration in which all nodes support the initial plurality. We consider a basic model in which the network is a clique and the update rule (called here the 3-majority dynamics) of the process is the following: each agent looks at the colors of three random neighbors and then applies the majority rule (breaking ties uniformly). We prove that the process converges in time O(min{k,(n/logn)1/3}logn) with high probability, provided that s⩾cmin{2k,(n/logn)1/3}nlogn. We then prove that our upper bound above is tight as long as k⩽(n/logn)1/4. This fact implies an exponential time-gap between the plurality-consensus process and the median process (see Doerr et al. in Proceedings of the 23rd annual ACM symposium on parallelism in algorithms and architectures (SPAA’11), pp 149–158. ACM, 2011). A natural question is whether looking at more (than three) random neighbors can significantly speed up the process. We provide a negative answer to this question: in particular, we show that samples of polylogarithmic size can speed up the process by a polylogarithmic factor only. More... »

PAGES

293-306

References to SciGraph publications

  • 2008-07. A simple population protocol for fast robust approximate majority in DISTRIBUTED COMPUTING
  • 2014. Determining Majority in Networks with Local Interactions and Very Small Local Memory in AUTOMATA, LANGUAGES, AND PROGRAMMING
  • 2014-05. Majority dynamics and aggregation of information in social networks in AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS
  • 2008. Biased Voting and the Democratic Primary Problem in INTERNET AND NETWORK ECONOMICS
  • 2013. Distributed Multivalued Consensus in COMPUTER AND INFORMATION SCIENCES III
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00446-016-0289-4

    DOI

    http://dx.doi.org/10.1007/s00446-016-0289-4

    DIMENSIONS

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


    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/0104", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Statistics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Sapienza Universit\u00e0 di Roma, Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Becchetti", 
            "givenName": "Luca", 
            "id": "sg:person.011301474260.17", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011301474260.17"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Rome Tor Vergata", 
              "id": "https://www.grid.ac/institutes/grid.6530.0", 
              "name": [
                "Universit\u00e0 Tor Vergata di Roma, Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Clementi", 
            "givenName": "Andrea", 
            "id": "sg:person.011027660123.21", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011027660123.21"
            ], 
            "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": "Natale", 
            "givenName": "Emanuele", 
            "id": "sg:person.013120403601.12", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013120403601.12"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Rome Tor Vergata", 
              "id": "https://www.grid.ac/institutes/grid.6530.0", 
              "name": [
                "Universit\u00e0 Tor Vergata di Roma, Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Pasquale", 
            "givenName": "Francesco", 
            "id": "sg:person.010366026047.55", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010366026047.55"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Silvestri", 
            "givenName": "Riccardo", 
            "id": "sg:person.012430640403.64", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012430640403.64"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of California, Berkeley", 
              "id": "https://www.grid.ac/institutes/grid.47840.3f", 
              "name": [
                "UC Berkeley, Berkeley, CA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Trevisan", 
            "givenName": "Luca", 
            "id": "sg:person.015761757701.03", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015761757701.03"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/j.spl.2013.12.009", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004852223"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4471-4594-3_28", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005263165", 
              "https://doi.org/10.1007/978-1-4471-4594-3_28"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1989493.1989516", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018294837"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-92185-1_70", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018780943", 
              "https://doi.org/10.1007/978-3-540-92185-1_70"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-92185-1_70", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018780943", 
              "https://doi.org/10.1007/978-3-540-92185-1_70"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2014.11.026", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020697136"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/(sici)1098-2418(199809)13:2<99::aid-rsa1>3.0.co;2-m", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029494978"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/inco.2001.3088", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032674722"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-43948-7_72", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037862493", 
              "https://doi.org/10.1007/978-3-662-43948-7_72"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10458-013-9230-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038615305", 
              "https://doi.org/10.1007/s10458-013-9230-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(01)00055-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043609997"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-008-0059-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047260056", 
              "https://doi.org/10.1007/s00446-008-0059-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-008-0059-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047260056", 
              "https://doi.org/10.1007/s00446-008-0059-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.dam.2014.07.026", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049770196"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.74.5148", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060811316"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.74.5148", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060811316"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/110823018", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062864573"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/icassp.2009.4960420", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094018886"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/infcom.2009.5062181", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095212433"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9780511761942", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098663531"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/mbk/058", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098774897"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2017-08", 
        "datePublishedReg": "2017-08-01", 
        "description": "We study a plurality-consensus process in which each of n anonymous agents of a communication network initially supports a color chosen from the set [k]. Then, in every round, each agent can revise his color according to the colors currently held by a random sample of his neighbors. It is assumed that the initial color configuration exhibits a sufficiently large biass towards a fixed plurality color, that is, the number of nodes supporting the plurality color exceeds the number of nodes supporting any other color by s additional nodes. The goal is having the process to converge to the stable configuration in which all nodes support the initial plurality. We consider a basic model in which the network is a clique and the update rule (called here the 3-majority dynamics) of the process is the following: each agent looks at the colors of three random neighbors and then applies the majority rule (breaking ties uniformly). We prove that the process converges in time O(min{k,(n/logn)1/3}logn) with high probability, provided that s\u2a7ecmin{2k,(n/logn)1/3}nlogn. We then prove that our upper bound above is tight as long as k\u2a7d(n/logn)1/4. This fact implies an exponential time-gap between the plurality-consensus process and the median process (see Doerr et al. in Proceedings of the 23rd annual ACM symposium on parallelism in algorithms and architectures (SPAA\u201911), pp 149\u2013158. ACM, 2011). A natural question is whether looking at more (than three) random neighbors can significantly speed up the process. We provide a negative answer to this question: in particular, we show that samples of polylogarithmic size can speed up the process by a polylogarithmic factor only.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00446-016-0289-4", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1052621", 
            "issn": [
              "0178-2770", 
              "1432-0452"
            ], 
            "name": "Distributed Computing", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "30"
          }
        ], 
        "name": "Simple dynamics for plurality consensus", 
        "pagination": "293-306", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "61eab4d290269f5f72ce5bcc0832b64440583f017921c0bdf3b27c4488ff8358"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00446-016-0289-4"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1020550006"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00446-016-0289-4", 
          "https://app.dimensions.ai/details/publication/pub.1020550006"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T12:26", 
        "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/0000000362_0000000362/records_87109_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs00446-016-0289-4"
      }
    ]
     

    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/s00446-016-0289-4'

    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/s00446-016-0289-4'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00446-016-0289-4'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00446-016-0289-4'


     

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

    166 TRIPLES      21 PREDICATES      45 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00446-016-0289-4 schema:about anzsrc-for:01
    2 anzsrc-for:0104
    3 schema:author N90aacf8aef334b278998cfcf079d1949
    4 schema:citation sg:pub.10.1007/978-1-4471-4594-3_28
    5 sg:pub.10.1007/978-3-540-92185-1_70
    6 sg:pub.10.1007/978-3-662-43948-7_72
    7 sg:pub.10.1007/s00446-008-0059-z
    8 sg:pub.10.1007/s10458-013-9230-4
    9 https://doi.org/10.1002/(sici)1098-2418(199809)13:2<99::aid-rsa1>3.0.co;2-m
    10 https://doi.org/10.1006/inco.2001.3088
    11 https://doi.org/10.1016/j.dam.2014.07.026
    12 https://doi.org/10.1016/j.spl.2013.12.009
    13 https://doi.org/10.1016/j.tcs.2014.11.026
    14 https://doi.org/10.1016/s0304-3975(01)00055-x
    15 https://doi.org/10.1017/cbo9780511761942
    16 https://doi.org/10.1090/mbk/058
    17 https://doi.org/10.1103/physrevlett.74.5148
    18 https://doi.org/10.1109/icassp.2009.4960420
    19 https://doi.org/10.1109/infcom.2009.5062181
    20 https://doi.org/10.1137/110823018
    21 https://doi.org/10.1145/1989493.1989516
    22 schema:datePublished 2017-08
    23 schema:datePublishedReg 2017-08-01
    24 schema:description We study a plurality-consensus process in which each of n anonymous agents of a communication network initially supports a color chosen from the set [k]. Then, in every round, each agent can revise his color according to the colors currently held by a random sample of his neighbors. It is assumed that the initial color configuration exhibits a sufficiently large biass towards a fixed plurality color, that is, the number of nodes supporting the plurality color exceeds the number of nodes supporting any other color by s additional nodes. The goal is having the process to converge to the stable configuration in which all nodes support the initial plurality. We consider a basic model in which the network is a clique and the update rule (called here the 3-majority dynamics) of the process is the following: each agent looks at the colors of three random neighbors and then applies the majority rule (breaking ties uniformly). We prove that the process converges in time O(min{k,(n/logn)1/3}logn) with high probability, provided that s⩾cmin{2k,(n/logn)1/3}nlogn. We then prove that our upper bound above is tight as long as k⩽(n/logn)1/4. This fact implies an exponential time-gap between the plurality-consensus process and the median process (see Doerr et al. in Proceedings of the 23rd annual ACM symposium on parallelism in algorithms and architectures (SPAA’11), pp 149–158. ACM, 2011). A natural question is whether looking at more (than three) random neighbors can significantly speed up the process. We provide a negative answer to this question: in particular, we show that samples of polylogarithmic size can speed up the process by a polylogarithmic factor only.
    25 schema:genre research_article
    26 schema:inLanguage en
    27 schema:isAccessibleForFree true
    28 schema:isPartOf N0a532a3e09af4e88b564886687a3c113
    29 Ne3e7c7d7c5e64b979a0fb52fd6e3de92
    30 sg:journal.1052621
    31 schema:name Simple dynamics for plurality consensus
    32 schema:pagination 293-306
    33 schema:productId N255c9d9cf12d4abd9748c1d1bae1f6c7
    34 N596c7b06a59a41a3b775de618c00929f
    35 N87b551d958794c88a7561f5c4cd50439
    36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020550006
    37 https://doi.org/10.1007/s00446-016-0289-4
    38 schema:sdDatePublished 2019-04-11T12:26
    39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    40 schema:sdPublisher N756a476da9954d75a2438298673b4b2b
    41 schema:url https://link.springer.com/10.1007%2Fs00446-016-0289-4
    42 sgo:license sg:explorer/license/
    43 sgo:sdDataset articles
    44 rdf:type schema:ScholarlyArticle
    45 N0a532a3e09af4e88b564886687a3c113 schema:issueNumber 4
    46 rdf:type schema:PublicationIssue
    47 N255c9d9cf12d4abd9748c1d1bae1f6c7 schema:name readcube_id
    48 schema:value 61eab4d290269f5f72ce5bcc0832b64440583f017921c0bdf3b27c4488ff8358
    49 rdf:type schema:PropertyValue
    50 N596c7b06a59a41a3b775de618c00929f schema:name dimensions_id
    51 schema:value pub.1020550006
    52 rdf:type schema:PropertyValue
    53 N6668d7e1320d42b28709f19b874f30dc rdf:first sg:person.012430640403.64
    54 rdf:rest Ncf0331afdd514947b87d2ca4ce4d881e
    55 N756a476da9954d75a2438298673b4b2b schema:name Springer Nature - SN SciGraph project
    56 rdf:type schema:Organization
    57 N87b551d958794c88a7561f5c4cd50439 schema:name doi
    58 schema:value 10.1007/s00446-016-0289-4
    59 rdf:type schema:PropertyValue
    60 N90aacf8aef334b278998cfcf079d1949 rdf:first sg:person.011301474260.17
    61 rdf:rest Ne436731bd9f541359fdd4caa76b7a3fc
    62 Na60055b2c6074a3db86de9ca28b3529e rdf:first sg:person.010366026047.55
    63 rdf:rest N6668d7e1320d42b28709f19b874f30dc
    64 Na672a8a6864b4b71a1847fb9db6a2b5a schema:name Rome, Italy
    65 rdf:type schema:Organization
    66 Nb03589ea297d462789e32c4b7a3b3016 rdf:first sg:person.013120403601.12
    67 rdf:rest Na60055b2c6074a3db86de9ca28b3529e
    68 Ncf0331afdd514947b87d2ca4ce4d881e rdf:first sg:person.015761757701.03
    69 rdf:rest rdf:nil
    70 Ne3e7c7d7c5e64b979a0fb52fd6e3de92 schema:volumeNumber 30
    71 rdf:type schema:PublicationVolume
    72 Ne436731bd9f541359fdd4caa76b7a3fc rdf:first sg:person.011027660123.21
    73 rdf:rest Nb03589ea297d462789e32c4b7a3b3016
    74 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    75 schema:name Mathematical Sciences
    76 rdf:type schema:DefinedTerm
    77 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
    78 schema:name Statistics
    79 rdf:type schema:DefinedTerm
    80 sg:journal.1052621 schema:issn 0178-2770
    81 1432-0452
    82 schema:name Distributed Computing
    83 rdf:type schema:Periodical
    84 sg:person.010366026047.55 schema:affiliation https://www.grid.ac/institutes/grid.6530.0
    85 schema:familyName Pasquale
    86 schema:givenName Francesco
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010366026047.55
    88 rdf:type schema:Person
    89 sg:person.011027660123.21 schema:affiliation https://www.grid.ac/institutes/grid.6530.0
    90 schema:familyName Clementi
    91 schema:givenName Andrea
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011027660123.21
    93 rdf:type schema:Person
    94 sg:person.011301474260.17 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    95 schema:familyName Becchetti
    96 schema:givenName Luca
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011301474260.17
    98 rdf:type schema:Person
    99 sg:person.012430640403.64 schema:affiliation Na672a8a6864b4b71a1847fb9db6a2b5a
    100 schema:familyName Silvestri
    101 schema:givenName Riccardo
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012430640403.64
    103 rdf:type schema:Person
    104 sg:person.013120403601.12 schema:affiliation https://www.grid.ac/institutes/grid.419528.3
    105 schema:familyName Natale
    106 schema:givenName Emanuele
    107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013120403601.12
    108 rdf:type schema:Person
    109 sg:person.015761757701.03 schema:affiliation https://www.grid.ac/institutes/grid.47840.3f
    110 schema:familyName Trevisan
    111 schema:givenName Luca
    112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015761757701.03
    113 rdf:type schema:Person
    114 sg:pub.10.1007/978-1-4471-4594-3_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005263165
    115 https://doi.org/10.1007/978-1-4471-4594-3_28
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/978-3-540-92185-1_70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018780943
    118 https://doi.org/10.1007/978-3-540-92185-1_70
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/978-3-662-43948-7_72 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037862493
    121 https://doi.org/10.1007/978-3-662-43948-7_72
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/s00446-008-0059-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1047260056
    124 https://doi.org/10.1007/s00446-008-0059-z
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/s10458-013-9230-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038615305
    127 https://doi.org/10.1007/s10458-013-9230-4
    128 rdf:type schema:CreativeWork
    129 https://doi.org/10.1002/(sici)1098-2418(199809)13:2<99::aid-rsa1>3.0.co;2-m schema:sameAs https://app.dimensions.ai/details/publication/pub.1029494978
    130 rdf:type schema:CreativeWork
    131 https://doi.org/10.1006/inco.2001.3088 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032674722
    132 rdf:type schema:CreativeWork
    133 https://doi.org/10.1016/j.dam.2014.07.026 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049770196
    134 rdf:type schema:CreativeWork
    135 https://doi.org/10.1016/j.spl.2013.12.009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004852223
    136 rdf:type schema:CreativeWork
    137 https://doi.org/10.1016/j.tcs.2014.11.026 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020697136
    138 rdf:type schema:CreativeWork
    139 https://doi.org/10.1016/s0304-3975(01)00055-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043609997
    140 rdf:type schema:CreativeWork
    141 https://doi.org/10.1017/cbo9780511761942 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098663531
    142 rdf:type schema:CreativeWork
    143 https://doi.org/10.1090/mbk/058 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098774897
    144 rdf:type schema:CreativeWork
    145 https://doi.org/10.1103/physrevlett.74.5148 schema:sameAs https://app.dimensions.ai/details/publication/pub.1060811316
    146 rdf:type schema:CreativeWork
    147 https://doi.org/10.1109/icassp.2009.4960420 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094018886
    148 rdf:type schema:CreativeWork
    149 https://doi.org/10.1109/infcom.2009.5062181 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095212433
    150 rdf:type schema:CreativeWork
    151 https://doi.org/10.1137/110823018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062864573
    152 rdf:type schema:CreativeWork
    153 https://doi.org/10.1145/1989493.1989516 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018294837
    154 rdf:type schema:CreativeWork
    155 https://www.grid.ac/institutes/grid.419528.3 schema:alternateName Max Planck Institute for Informatics
    156 schema:name Max Planck Institute for Informatics, Saarbrücken, Germany
    157 rdf:type schema:Organization
    158 https://www.grid.ac/institutes/grid.47840.3f schema:alternateName University of California, Berkeley
    159 schema:name UC Berkeley, Berkeley, CA, USA
    160 rdf:type schema:Organization
    161 https://www.grid.ac/institutes/grid.6530.0 schema:alternateName University of Rome Tor Vergata
    162 schema:name Università Tor Vergata di Roma, Rome, Italy
    163 rdf:type schema:Organization
    164 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
    165 schema:name Sapienza Università di Roma, Rome, Italy
    166 rdf:type schema:Organization
     




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


    ...