On the Communication Complexity of Linear Algebraic Problems in the Message Passing Model View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2014

AUTHORS

Yi Li , Xiaoming Sun , Chengu Wang , David P. Woodruff

ABSTRACT

We study the communication complexity of linear algebraic problems over finite fields in the multi-player message passing model, proving a number of tight lower bounds. We give a general framework for reducing these multi-player problems to their two-player counterparts, showing that the randomized s-player communication complexity of these problems is at least s times the randomized two-player communication complexity. Provided the problem has a certain amount of algebraic symmetry, we can show the hardest input distribution is a symmetric distribution, and therefore apply a recent multi-player lower bound technique of Phillips et al. Further, we give new two-player lower bounds for a number of these problems. In particular, our optimal lower bound for the two-player version of the matrix rank problem resolves an open question of Sun and Wang.A common feature of our lower bounds is that they apply even to the special “threshold promise” versions of these problems, wherein the underlying quantity, e.g., rank, is promised to be one of just two values, one on each side of some critical threshold. These kinds of promise problems are commonplace in the literature on data streaming as sources of hardness for reductions giving space lower bounds. More... »

PAGES

499-513

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-45174-8_34

DOI

http://dx.doi.org/10.1007/978-3-662-45174-8_34

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Max-Planck Institute for Informatics, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck Institute for Informatics, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Li", 
        "givenName": "Yi", 
        "id": "sg:person.07361330656.72", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07361330656.72"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Computing Technology, Chinese Academy of Sciences, China", 
          "id": "http://www.grid.ac/institutes/grid.424936.e", 
          "name": [
            "Institute of Computing Technology, Chinese Academy of Sciences, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sun", 
        "givenName": "Xiaoming", 
        "id": "sg:person.012040246065.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012040246065.08"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Google Inc., USA", 
          "id": "http://www.grid.ac/institutes/grid.420451.6", 
          "name": [
            "Google Inc., USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Chengu", 
        "id": "sg:person.013312112022.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013312112022.08"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Almaden Research Center, USA", 
          "id": "http://www.grid.ac/institutes/grid.481551.c", 
          "name": [
            "IBM Almaden Research Center, 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": "2014", 
    "datePublishedReg": "2014-01-01", 
    "description": "We study the communication complexity of linear algebraic problems over finite fields in the multi-player message passing model, proving a number of tight lower bounds. We give a general framework for reducing these multi-player problems to their two-player counterparts, showing that the randomized s-player communication complexity of these problems is at least s times the randomized two-player communication complexity. Provided the problem has a certain amount of algebraic symmetry, we can show the hardest input distribution is a symmetric distribution, and therefore apply a recent multi-player lower bound technique of Phillips et al. Further, we give new two-player lower bounds for a number of these problems. In particular, our optimal lower bound for the two-player version of the matrix rank problem resolves an open question of Sun and Wang.A common feature of our lower bounds is that they apply even to the special \u201cthreshold promise\u201d versions of these problems, wherein the underlying quantity, e.g., rank, is promised to be one of just two values, one on each side of some critical threshold. These kinds of promise problems are commonplace in the literature on data streaming as sources of hardness for reductions giving space lower bounds.", 
    "editor": [
      {
        "familyName": "Kuhn", 
        "givenName": "Fabian", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-45174-8_34", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-662-45173-1", 
        "978-3-662-45174-8"
      ], 
      "name": "Distributed Computing", 
      "type": "Book"
    }, 
    "keywords": [
      "linear algebraic problem", 
      "lower bounds", 
      "algebraic problem", 
      "communication complexity", 
      "space lower bounds", 
      "tight lower bounds", 
      "algebraic symmetries", 
      "source of hardness", 
      "two-player version", 
      "finite field", 
      "Message Passing Model", 
      "promise problem", 
      "symmetric distribution", 
      "rank problem", 
      "bounds", 
      "input distribution", 
      "general framework", 
      "problem", 
      "complexity", 
      "open question", 
      "critical threshold", 
      "et al", 
      "symmetry", 
      "s time", 
      "model", 
      "version", 
      "distribution", 
      "Wang", 
      "field", 
      "Phillips et al", 
      "Sun", 
      "number", 
      "rank", 
      "certain amount", 
      "quantity", 
      "framework", 
      "technique", 
      "al", 
      "kind", 
      "common feature", 
      "counterparts", 
      "threshold", 
      "values", 
      "features", 
      "time", 
      "data", 
      "literature", 
      "source", 
      "side", 
      "questions", 
      "reduction", 
      "messages", 
      "amount", 
      "promise", 
      "hardness"
    ], 
    "name": "On the Communication Complexity of Linear Algebraic Problems in the Message Passing Model", 
    "pagination": "499-513", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1018675379"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-45174-8_34"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-45174-8_34", 
      "https://app.dimensions.ai/details/publication/pub.1018675379"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:47", 
    "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_18.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-45174-8_34"
  }
]
 

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-45174-8_34'

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-45174-8_34'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-45174-8_34'

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-45174-8_34'


 

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

144 TRIPLES      22 PREDICATES      80 URIs      73 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-45174-8_34 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N99b8241c2ca24339adbf37fe3809917f
4 schema:datePublished 2014
5 schema:datePublishedReg 2014-01-01
6 schema:description We study the communication complexity of linear algebraic problems over finite fields in the multi-player message passing model, proving a number of tight lower bounds. We give a general framework for reducing these multi-player problems to their two-player counterparts, showing that the randomized s-player communication complexity of these problems is at least s times the randomized two-player communication complexity. Provided the problem has a certain amount of algebraic symmetry, we can show the hardest input distribution is a symmetric distribution, and therefore apply a recent multi-player lower bound technique of Phillips et al. Further, we give new two-player lower bounds for a number of these problems. In particular, our optimal lower bound for the two-player version of the matrix rank problem resolves an open question of Sun and Wang.A common feature of our lower bounds is that they apply even to the special “threshold promise” versions of these problems, wherein the underlying quantity, e.g., rank, is promised to be one of just two values, one on each side of some critical threshold. These kinds of promise problems are commonplace in the literature on data streaming as sources of hardness for reductions giving space lower bounds.
7 schema:editor N7a667d20b4754065a627e315b9a2dbea
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Neaf983648fa64b8397f0e4955aa130d6
11 schema:keywords Message Passing Model
12 Phillips et al
13 Sun
14 Wang
15 al
16 algebraic problem
17 algebraic symmetries
18 amount
19 bounds
20 certain amount
21 common feature
22 communication complexity
23 complexity
24 counterparts
25 critical threshold
26 data
27 distribution
28 et al
29 features
30 field
31 finite field
32 framework
33 general framework
34 hardness
35 input distribution
36 kind
37 linear algebraic problem
38 literature
39 lower bounds
40 messages
41 model
42 number
43 open question
44 problem
45 promise
46 promise problem
47 quantity
48 questions
49 rank
50 rank problem
51 reduction
52 s time
53 side
54 source
55 source of hardness
56 space lower bounds
57 symmetric distribution
58 symmetry
59 technique
60 threshold
61 tight lower bounds
62 time
63 two-player version
64 values
65 version
66 schema:name On the Communication Complexity of Linear Algebraic Problems in the Message Passing Model
67 schema:pagination 499-513
68 schema:productId N906955838d014a7d9bc1f7eb33579858
69 Nfe083676f05641f88d5364ad380792b0
70 schema:publisher N156ed8d22e374459bece1ca35bbe5417
71 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018675379
72 https://doi.org/10.1007/978-3-662-45174-8_34
73 schema:sdDatePublished 2022-12-01T06:47
74 schema:sdLicense https://scigraph.springernature.com/explorer/license/
75 schema:sdPublisher Ne284adc8e09a47448114f2e3c7c47545
76 schema:url https://doi.org/10.1007/978-3-662-45174-8_34
77 sgo:license sg:explorer/license/
78 sgo:sdDataset chapters
79 rdf:type schema:Chapter
80 N156ed8d22e374459bece1ca35bbe5417 schema:name Springer Nature
81 rdf:type schema:Organisation
82 N23c536227c4e49678d12ea74263405ff rdf:first sg:person.012040246065.08
83 rdf:rest N30823828c21f4454874e4455cef75a8e
84 N30823828c21f4454874e4455cef75a8e rdf:first sg:person.013312112022.08
85 rdf:rest Nf386fde786a64fe4b00186b0f9ffd10e
86 N7a667d20b4754065a627e315b9a2dbea rdf:first Naae20add31f448daae2471ecfb1c2f38
87 rdf:rest rdf:nil
88 N906955838d014a7d9bc1f7eb33579858 schema:name doi
89 schema:value 10.1007/978-3-662-45174-8_34
90 rdf:type schema:PropertyValue
91 N99b8241c2ca24339adbf37fe3809917f rdf:first sg:person.07361330656.72
92 rdf:rest N23c536227c4e49678d12ea74263405ff
93 Naae20add31f448daae2471ecfb1c2f38 schema:familyName Kuhn
94 schema:givenName Fabian
95 rdf:type schema:Person
96 Ne284adc8e09a47448114f2e3c7c47545 schema:name Springer Nature - SN SciGraph project
97 rdf:type schema:Organization
98 Neaf983648fa64b8397f0e4955aa130d6 schema:isbn 978-3-662-45173-1
99 978-3-662-45174-8
100 schema:name Distributed Computing
101 rdf:type schema:Book
102 Nf386fde786a64fe4b00186b0f9ffd10e rdf:first sg:person.012727410605.86
103 rdf:rest rdf:nil
104 Nfe083676f05641f88d5364ad380792b0 schema:name dimensions_id
105 schema:value pub.1018675379
106 rdf:type schema:PropertyValue
107 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
108 schema:name Mathematical Sciences
109 rdf:type schema:DefinedTerm
110 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
111 schema:name Pure Mathematics
112 rdf:type schema:DefinedTerm
113 sg:person.012040246065.08 schema:affiliation grid-institutes:grid.424936.e
114 schema:familyName Sun
115 schema:givenName Xiaoming
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012040246065.08
117 rdf:type schema:Person
118 sg:person.012727410605.86 schema:affiliation grid-institutes:grid.481551.c
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 sg:person.013312112022.08 schema:affiliation grid-institutes:grid.420451.6
124 schema:familyName Wang
125 schema:givenName Chengu
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013312112022.08
127 rdf:type schema:Person
128 sg:person.07361330656.72 schema:affiliation grid-institutes:grid.419528.3
129 schema:familyName Li
130 schema:givenName Yi
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07361330656.72
132 rdf:type schema:Person
133 grid-institutes:grid.419528.3 schema:alternateName Max-Planck Institute for Informatics, Germany
134 schema:name Max-Planck Institute for Informatics, Germany
135 rdf:type schema:Organization
136 grid-institutes:grid.420451.6 schema:alternateName Google Inc., USA
137 schema:name Google Inc., USA
138 rdf:type schema:Organization
139 grid-institutes:grid.424936.e schema:alternateName Institute of Computing Technology, Chinese Academy of Sciences, China
140 schema:name Institute of Computing Technology, Chinese Academy of Sciences, China
141 rdf:type schema:Organization
142 grid-institutes:grid.481551.c schema:alternateName IBM Almaden Research Center, USA
143 schema:name IBM Almaden Research Center, USA
144 rdf:type schema:Organization
 




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


...