The Simultaneous Communication of Disjointness with Applications to Data Streams View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2015-06-20

AUTHORS

Omri Weinstein , David P. Woodruff

ABSTRACT

We study k-party number-in-hand set disjointness in the simultaneous message-passing model, and show that even if each element i∈[n]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$i\in [n]$$ \end{document} is guaranteed to either belong to all k parties or to at most O(1) parties in expectation (and to at most O(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$O(\log n)$$ \end{document} parties with high probability), then Ω(nmin(log1/δ,logk)/k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\varOmega (n \min (\log 1/\delta , \log k) / k )$$ \end{document} communication is required by any δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\delta $$ \end{document}-error communication protocol for this problem (assuming k=Ω(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$k = \varOmega (\log n)$$ \end{document}).We use the strong promise of our lower bound, together with a recent characterization of turnstile streaming algorithms as linear sketches, to obtain new lower bounds for the well-studied problem in data streams of approximating the frequency moments. We obtain a space lower bound of Ω(n1-2/pε-2logMlog1/δ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\varOmega (n^{1-2/p} \varepsilon ^{-2} \log M \log 1/\delta )$$ \end{document} bits for any algorithm giving a (1+ε)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$(1+\varepsilon )$$ \end{document}-approximation to the p-th moment ∑i=1n|xi|p\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\sum _{i=1}^n |x_i|^p$$ \end{document} of an n-dimensional vector x∈{±M}n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$x\in \{\pm M\}^n$$ \end{document} with probability 1-δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$1-\delta $$ \end{document}, for any δ≥2-o(n1/p)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\delta \ge 2^{-o(n^{1/p})}$$ \end{document}. Our lower bound improves upon a prior Ω(n1-2/pε-2logM)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\varOmega (n^{1-2/p} \varepsilon ^{-2} \log M)$$ \end{document} lower bound which did not capture the dependence on δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\delta $$ \end{document}, and our bound is optimal whenever ε≤1/poly(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\varepsilon \le 1/\text {poly}(\log n)$$ \end{document}. This is the first example of a lower bound in data streams which uses a characterization in terms of linear sketches to obtain stronger lower bounds than obtainable via the one-way communication model; indeed, our set disjointness lower bound provably cannot hold in the one-way model. More... »

PAGES

1082-1093

Book

TITLE

Automata, Languages, and Programming

ISBN

978-3-662-47671-0
978-3-662-47672-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-47672-7_88

DOI

http://dx.doi.org/10.1007/978-3-662-47672-7_88

DIMENSIONS

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


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/10", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Technology", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1005", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Communications Technologies", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Princeton University, 08544, Princeton, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.16750.35", 
          "name": [
            "Princeton University, 08544, Princeton, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Weinstein", 
        "givenName": "Omri", 
        "id": "sg:person.011240404143.15", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011240404143.15"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Research, Almaden, San Jose, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM Research, Almaden, San Jose, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Woodruff", 
        "givenName": "David P.", 
        "id": "sg:person.012727410605.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-06-20", 
    "datePublishedReg": "2015-06-20", 
    "description": "We study k-party number-in-hand set disjointness in the simultaneous message-passing model, and show that even if each element i\u2208[n]\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$i\\in [n]$$\n\\end{document} is guaranteed to either belong to all k parties or to at most O(1) parties in expectation (and to at most O(logn)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$O(\\log n)$$\n\\end{document} parties with high probability), then \u03a9(nmin(log1/\u03b4,logk)/k)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$\\varOmega (n \\min (\\log 1/\\delta , \\log k) / k )$$\n\\end{document} communication is required by any \u03b4\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$\\delta $$\n\\end{document}-error communication protocol for this problem (assuming k=\u03a9(logn)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$k = \\varOmega (\\log n)$$\n\\end{document}).We use the strong promise of our lower bound, together with a recent characterization of turnstile streaming algorithms as linear sketches, to obtain new lower bounds for the well-studied problem in data streams of approximating the frequency moments. We obtain a space lower bound of \u03a9(n1-2/p\u03b5-2logMlog1/\u03b4)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$\\varOmega (n^{1-2/p} \\varepsilon ^{-2} \\log M \\log 1/\\delta )$$\n\\end{document} bits for any algorithm giving a (1+\u03b5)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$(1+\\varepsilon )$$\n\\end{document}-approximation to the p-th moment \u2211i=1n|xi|p\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$\\sum _{i=1}^n |x_i|^p$$\n\\end{document} of an n-dimensional vector x\u2208{\u00b1M}n\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$x\\in \\{\\pm M\\}^n$$\n\\end{document} with probability 1-\u03b4\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$1-\\delta $$\n\\end{document}, for any \u03b4\u22652-o(n1/p)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$\\delta \\ge 2^{-o(n^{1/p})}$$\n\\end{document}. Our lower bound improves upon a prior \u03a9(n1-2/p\u03b5-2logM)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$\\varOmega (n^{1-2/p} \\varepsilon ^{-2} \\log M)$$\n\\end{document} lower bound which did not capture the dependence on \u03b4\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$\\delta $$\n\\end{document}, and our bound is optimal whenever \u03b5\u22641/poly(logn)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$\\varepsilon \\le 1/\\text {poly}(\\log n)$$\n\\end{document}. This is the first example of a lower bound in data streams which uses a characterization in terms of linear sketches to obtain stronger lower bounds than obtainable via the one-way communication model; indeed, our set disjointness lower bound provably cannot hold in the one-way model.", 
    "editor": [
      {
        "familyName": "Halld\u00f3rsson", 
        "givenName": "Magn\u00fas M.", 
        "type": "Person"
      }, 
      {
        "familyName": "Iwama", 
        "givenName": "Kazuo", 
        "type": "Person"
      }, 
      {
        "familyName": "Kobayashi", 
        "givenName": "Naoki", 
        "type": "Person"
      }, 
      {
        "familyName": "Speckmann", 
        "givenName": "Bettina", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-47672-7_88", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-662-47671-0", 
        "978-3-662-47672-7"
      ], 
      "name": "Automata, Languages, and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "one-way communication model", 
      "simultaneous communication", 
      "expectations", 
      "communication", 
      "communication protocols", 
      "strong promise", 
      "data streams", 
      "communication model", 
      "model", 
      "problem", 
      "streams", 
      "sketch", 
      "parties", 
      "promise", 
      "characterization", 
      "protocol", 
      "recent characterization", 
      "moment", 
      "dimensional vector", 
      "terms", 
      "one-way model", 
      "applications", 
      "number", 
      "elements", 
      "turnstile", 
      "algorithm", 
      "lower bounds", 
      "space", 
      "vector", 
      "first example", 
      "example", 
      "disjointness", 
      "k parties", 
      "bounds", 
      "dependence", 
      "message-passing model", 
      "linear", 
      "new lower bounds", 
      "frequency moments", 
      "approximation", 
      "probability 1", 
      "strong lower bounds", 
      "Set Disjointness", 
      "linear sketches"
    ], 
    "name": "The Simultaneous Communication of Disjointness with Applications to Data Streams", 
    "pagination": "1082-1093", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1016316224"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-47672-7_88"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-47672-7_88", 
      "https://app.dimensions.ai/details/publication/pub.1016316224"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:51", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_33.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-47672-7_88"
  }
]
 

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-662-47672-7_88'

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-662-47672-7_88'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-47672-7_88'

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-662-47672-7_88'


 

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

128 TRIPLES      22 PREDICATES      68 URIs      61 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-47672-7_88 schema:about anzsrc-for:10
2 anzsrc-for:1005
3 schema:author N08b77924055e42ad9c93cc48feca9178
4 schema:datePublished 2015-06-20
5 schema:datePublishedReg 2015-06-20
6 schema:description We study k-party number-in-hand set disjointness in the simultaneous message-passing model, and show that even if each element i∈[n]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$i\in [n]$$ \end{document} is guaranteed to either belong to all k parties or to at most O(1) parties in expectation (and to at most O(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$O(\log n)$$ \end{document} parties with high probability), then Ω(nmin(log1/δ,logk)/k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\varOmega (n \min (\log 1/\delta , \log k) / k )$$ \end{document} communication is required by any δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\delta $$ \end{document}-error communication protocol for this problem (assuming k=Ω(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$k = \varOmega (\log n)$$ \end{document}).We use the strong promise of our lower bound, together with a recent characterization of turnstile streaming algorithms as linear sketches, to obtain new lower bounds for the well-studied problem in data streams of approximating the frequency moments. We obtain a space lower bound of Ω(n1-2/pε-2logMlog1/δ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\varOmega (n^{1-2/p} \varepsilon ^{-2} \log M \log 1/\delta )$$ \end{document} bits for any algorithm giving a (1+ε)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$(1+\varepsilon )$$ \end{document}-approximation to the p-th moment ∑i=1n|xi|p\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\sum _{i=1}^n |x_i|^p$$ \end{document} of an n-dimensional vector x∈{±M}n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$x\in \{\pm M\}^n$$ \end{document} with probability 1-δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$1-\delta $$ \end{document}, for any δ≥2-o(n1/p)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\delta \ge 2^{-o(n^{1/p})}$$ \end{document}. Our lower bound improves upon a prior Ω(n1-2/pε-2logM)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\varOmega (n^{1-2/p} \varepsilon ^{-2} \log M)$$ \end{document} lower bound which did not capture the dependence on δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\delta $$ \end{document}, and our bound is optimal whenever ε≤1/poly(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\varepsilon \le 1/\text {poly}(\log n)$$ \end{document}. This is the first example of a lower bound in data streams which uses a characterization in terms of linear sketches to obtain stronger lower bounds than obtainable via the one-way communication model; indeed, our set disjointness lower bound provably cannot hold in the one-way model.
7 schema:editor N859ebfb9336a447797377de48f0bf174
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N2907c45174ac48238225db6fd28ea955
11 schema:keywords Set Disjointness
12 algorithm
13 applications
14 approximation
15 bounds
16 characterization
17 communication
18 communication model
19 communication protocols
20 data streams
21 dependence
22 dimensional vector
23 disjointness
24 elements
25 example
26 expectations
27 first example
28 frequency moments
29 k parties
30 linear
31 linear sketches
32 lower bounds
33 message-passing model
34 model
35 moment
36 new lower bounds
37 number
38 one-way communication model
39 one-way model
40 parties
41 probability 1
42 problem
43 promise
44 protocol
45 recent characterization
46 simultaneous communication
47 sketch
48 space
49 streams
50 strong lower bounds
51 strong promise
52 terms
53 turnstile
54 vector
55 schema:name The Simultaneous Communication of Disjointness with Applications to Data Streams
56 schema:pagination 1082-1093
57 schema:productId N10b2a68df39940a08883fabb46730437
58 Nd0339310ceda41c487a967b2e734b791
59 schema:publisher N0b5449334cf845a3b90f3b70a09aff12
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016316224
61 https://doi.org/10.1007/978-3-662-47672-7_88
62 schema:sdDatePublished 2022-12-01T06:51
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher N2de6291438d24af2bd872795e9c3ad4f
65 schema:url https://doi.org/10.1007/978-3-662-47672-7_88
66 sgo:license sg:explorer/license/
67 sgo:sdDataset chapters
68 rdf:type schema:Chapter
69 N08b77924055e42ad9c93cc48feca9178 rdf:first sg:person.011240404143.15
70 rdf:rest N93ab293a5b9d4cd7827237caa5d116db
71 N0b5449334cf845a3b90f3b70a09aff12 schema:name Springer Nature
72 rdf:type schema:Organisation
73 N10b2a68df39940a08883fabb46730437 schema:name doi
74 schema:value 10.1007/978-3-662-47672-7_88
75 rdf:type schema:PropertyValue
76 N134804e74fcd4fbba96ee92bd9d44696 rdf:first N86534fcb24c84e67bfc09fa6c32d2d6c
77 rdf:rest rdf:nil
78 N2907c45174ac48238225db6fd28ea955 schema:isbn 978-3-662-47671-0
79 978-3-662-47672-7
80 schema:name Automata, Languages, and Programming
81 rdf:type schema:Book
82 N2de6291438d24af2bd872795e9c3ad4f schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 N3bf186c8c1a7463ba88ff873e06e7e67 rdf:first N57bc229c9b55417d81f9d0dbf2b23e84
85 rdf:rest N134804e74fcd4fbba96ee92bd9d44696
86 N57bc229c9b55417d81f9d0dbf2b23e84 schema:familyName Kobayashi
87 schema:givenName Naoki
88 rdf:type schema:Person
89 N797ada9a76634b4f89865bf0ff5794e6 schema:familyName Iwama
90 schema:givenName Kazuo
91 rdf:type schema:Person
92 N859ebfb9336a447797377de48f0bf174 rdf:first Nab7b39dfc3ca49ac912ed9f4c9678167
93 rdf:rest N88442c15eb624b2682633fa63b911396
94 N86534fcb24c84e67bfc09fa6c32d2d6c schema:familyName Speckmann
95 schema:givenName Bettina
96 rdf:type schema:Person
97 N88442c15eb624b2682633fa63b911396 rdf:first N797ada9a76634b4f89865bf0ff5794e6
98 rdf:rest N3bf186c8c1a7463ba88ff873e06e7e67
99 N93ab293a5b9d4cd7827237caa5d116db rdf:first sg:person.012727410605.86
100 rdf:rest rdf:nil
101 Nab7b39dfc3ca49ac912ed9f4c9678167 schema:familyName Halldórsson
102 schema:givenName Magnús M.
103 rdf:type schema:Person
104 Nd0339310ceda41c487a967b2e734b791 schema:name dimensions_id
105 schema:value pub.1016316224
106 rdf:type schema:PropertyValue
107 anzsrc-for:10 schema:inDefinedTermSet anzsrc-for:
108 schema:name Technology
109 rdf:type schema:DefinedTerm
110 anzsrc-for:1005 schema:inDefinedTermSet anzsrc-for:
111 schema:name Communications Technologies
112 rdf:type schema:DefinedTerm
113 sg:person.011240404143.15 schema:affiliation grid-institutes:grid.16750.35
114 schema:familyName Weinstein
115 schema:givenName Omri
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011240404143.15
117 rdf:type schema:Person
118 sg:person.012727410605.86 schema:affiliation grid-institutes:grid.481554.9
119 schema:familyName Woodruff
120 schema:givenName David P.
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86
122 rdf:type schema:Person
123 grid-institutes:grid.16750.35 schema:alternateName Princeton University, 08544, Princeton, NJ, USA
124 schema:name Princeton University, 08544, Princeton, NJ, USA
125 rdf:type schema:Organization
126 grid-institutes:grid.481554.9 schema:alternateName IBM Research, Almaden, San Jose, CA, USA
127 schema:name IBM Research, Almaden, San Jose, CA, USA
128 rdf:type schema:Organization
 




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


...