Amplification of One-Way Information Complexity via Codes and Noise Sensitivity View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2015-06-20

AUTHORS

Marco Molinaro , David P. Woodruff , Grigory Yaroslavtsev

ABSTRACT

We show a new connection between the information complexity of one-way communication problems under product distributions and a relaxed notion of list-decodable codes. As a consequence, we obtain a characterization of the information complexity of one-way problems under product distributions for any error rate based on covering numbers. This generalizes the characterization via VC dimension for constant error rates given by Kremer, Nisan, and Ron (CCC, 1999). It also provides an exponential improvement in the error rate, yielding tight bounds for a number of problems. In addition, our framework gives a new technique for analyzing the complexity of composition (e.g., XOR and OR) of one-way communication problems, connecting the difficulty of these problems to the noise sensitivity of the composing function. Using this connection, we strengthen the lower bounds obtained by Molinaro, Woodruff and Yaroslavtsev (SODA, 2013) for several problems in the distributed and streaming models, obtaining optimal lower bounds for finding the approximate closest pair of a set of points and the approximate largest entry in a matrix product. Finally, to illustrate the utility and simplicity of our framework, we show how it unifies proofs of existing 1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1$$\end{document}-way lower bounds for sparse set disjointness, the indexing problem, the greater than function under product distributions, and the gap-Hamming problem under the uniform distribution. More... »

PAGES

960-972

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Delft University of Technology, Delft, The Netherlands", 
          "id": "http://www.grid.ac/institutes/grid.5292.c", 
          "name": [
            "Delft University of Technology, Delft, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Molinaro", 
        "givenName": "Marco", 
        "id": "sg:person.07522711725.87", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07522711725.87"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Almaden Research Center, San Jose, USA", 
          "id": "http://www.grid.ac/institutes/grid.481551.c", 
          "name": [
            "IBM Almaden Research Center, San Jose, 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"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Pennsylvania, Philadelphia, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.25879.31", 
          "name": [
            "University of Pennsylvania, Philadelphia, PA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yaroslavtsev", 
        "givenName": "Grigory", 
        "id": "sg:person.015277345473.26", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015277345473.26"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-06-20", 
    "datePublishedReg": "2015-06-20", 
    "description": "We show a new connection between the information complexity of one-way communication problems under product distributions and a relaxed notion of list-decodable codes. As a consequence, we obtain a characterization of the information complexity of one-way problems under product distributions for any error rate based on covering numbers. This generalizes the characterization via VC dimension for constant error rates given by Kremer, Nisan, and Ron (CCC, 1999). It also provides an exponential improvement in the error rate, yielding tight bounds for a number of problems. In addition, our framework gives a new technique for analyzing the complexity of composition (e.g., XOR and OR) of one-way communication problems, connecting the difficulty of these problems to the noise sensitivity of the composing function. Using this connection, we strengthen the lower bounds obtained by Molinaro, Woodruff and Yaroslavtsev (SODA, 2013) for several problems in the distributed and streaming models, obtaining optimal lower bounds for finding the approximate closest pair of a set of points and the approximate largest entry in a matrix product. Finally, to illustrate the utility and simplicity of our framework, we show how it unifies proofs of existing 1\\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}$$1$$\\end{document}-way lower bounds for sparse set disjointness, the indexing problem, the greater than function under product distributions, and the gap-Hamming problem under the uniform distribution.", 
    "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_78", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-662-47671-0", 
        "978-3-662-47672-7"
      ], 
      "name": "Automata, Languages, and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "information complexity", 
      "error rate", 
      "constant error rate", 
      "one-way problem", 
      "communication problems", 
      "indexing problem", 
      "lower bounds", 
      "relaxed notion", 
      "list-decodable codes", 
      "complexity of composition", 
      "VC dimension", 
      "exponential improvement", 
      "set of points", 
      "noise sensitivity", 
      "complexity", 
      "tight bounds", 
      "number of problems", 
      "optimal lower bounds", 
      "largest entry", 
      "code", 
      "new connections", 
      "framework", 
      "matrix product", 
      "close pairs", 
      "bounds", 
      "new technique", 
      "disjointness", 
      "set", 
      "Molinaro", 
      "connection", 
      "proof", 
      "Nisan", 
      "simplicity", 
      "technique", 
      "number", 
      "model", 
      "notion", 
      "difficulties", 
      "utility", 
      "improvement", 
      "point", 
      "function", 
      "dimensions", 
      "pairs", 
      "uniform distribution", 
      "entry", 
      "distribution", 
      "rate", 
      "addition", 
      "products", 
      "Kremer", 
      "Woodruff", 
      "consequences", 
      "sensitivity", 
      "product distribution", 
      "RON", 
      "characterization", 
      "composition", 
      "problem", 
      "amplification"
    ], 
    "name": "Amplification of One-Way Information Complexity via Codes and Noise Sensitivity", 
    "pagination": "960-972", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1037020507"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-47672-7_78"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-47672-7_78", 
      "https://app.dimensions.ai/details/publication/pub.1037020507"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:13", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_189.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-47672-7_78"
  }
]
 

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_78'

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_78'

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_78'

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_78'


 

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

154 TRIPLES      22 PREDICATES      84 URIs      77 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-47672-7_78 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nf26b2050e3a14e728f32c4718edeaa4c
4 schema:datePublished 2015-06-20
5 schema:datePublishedReg 2015-06-20
6 schema:description We show a new connection between the information complexity of one-way communication problems under product distributions and a relaxed notion of list-decodable codes. As a consequence, we obtain a characterization of the information complexity of one-way problems under product distributions for any error rate based on covering numbers. This generalizes the characterization via VC dimension for constant error rates given by Kremer, Nisan, and Ron (CCC, 1999). It also provides an exponential improvement in the error rate, yielding tight bounds for a number of problems. In addition, our framework gives a new technique for analyzing the complexity of composition (e.g., XOR and OR) of one-way communication problems, connecting the difficulty of these problems to the noise sensitivity of the composing function. Using this connection, we strengthen the lower bounds obtained by Molinaro, Woodruff and Yaroslavtsev (SODA, 2013) for several problems in the distributed and streaming models, obtaining optimal lower bounds for finding the approximate closest pair of a set of points and the approximate largest entry in a matrix product. Finally, to illustrate the utility and simplicity of our framework, we show how it unifies proofs of existing 1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1$$\end{document}-way lower bounds for sparse set disjointness, the indexing problem, the greater than function under product distributions, and the gap-Hamming problem under the uniform distribution.
7 schema:editor N35b716d6f9ba465e9b19385f98ce38a6
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N0fca0f9443834a4293189312f1ed0695
11 schema:keywords Kremer
12 Molinaro
13 Nisan
14 RON
15 VC dimension
16 Woodruff
17 addition
18 amplification
19 bounds
20 characterization
21 close pairs
22 code
23 communication problems
24 complexity
25 complexity of composition
26 composition
27 connection
28 consequences
29 constant error rate
30 difficulties
31 dimensions
32 disjointness
33 distribution
34 entry
35 error rate
36 exponential improvement
37 framework
38 function
39 improvement
40 indexing problem
41 information complexity
42 largest entry
43 list-decodable codes
44 lower bounds
45 matrix product
46 model
47 new connections
48 new technique
49 noise sensitivity
50 notion
51 number
52 number of problems
53 one-way problem
54 optimal lower bounds
55 pairs
56 point
57 problem
58 product distribution
59 products
60 proof
61 rate
62 relaxed notion
63 sensitivity
64 set
65 set of points
66 simplicity
67 technique
68 tight bounds
69 uniform distribution
70 utility
71 schema:name Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
72 schema:pagination 960-972
73 schema:productId N358014139df443628c425d055ecd0ff3
74 Ndb8fc587526d49fa9ccf13d76975c819
75 schema:publisher N7e3e2b47162348c6a78c1bce37372126
76 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037020507
77 https://doi.org/10.1007/978-3-662-47672-7_78
78 schema:sdDatePublished 2022-11-24T21:13
79 schema:sdLicense https://scigraph.springernature.com/explorer/license/
80 schema:sdPublisher N3c8b457b2ba3466d93c94fda1934cae1
81 schema:url https://doi.org/10.1007/978-3-662-47672-7_78
82 sgo:license sg:explorer/license/
83 sgo:sdDataset chapters
84 rdf:type schema:Chapter
85 N0f0ebe1d13034cb9a4ccb34765523743 rdf:first N12dfbc2558364fbcbe8c4cd89e5ddec1
86 rdf:rest Nbffc63ed9f6847129da8f3fc11460995
87 N0fca0f9443834a4293189312f1ed0695 schema:isbn 978-3-662-47671-0
88 978-3-662-47672-7
89 schema:name Automata, Languages, and Programming
90 rdf:type schema:Book
91 N12dfbc2558364fbcbe8c4cd89e5ddec1 schema:familyName Kobayashi
92 schema:givenName Naoki
93 rdf:type schema:Person
94 N2e0c17f3405243f7bb01a0e3f70b9b18 schema:familyName Iwama
95 schema:givenName Kazuo
96 rdf:type schema:Person
97 N358014139df443628c425d055ecd0ff3 schema:name doi
98 schema:value 10.1007/978-3-662-47672-7_78
99 rdf:type schema:PropertyValue
100 N35b716d6f9ba465e9b19385f98ce38a6 rdf:first Nd5052c0c3e9f47b0afa2b7772ff48d64
101 rdf:rest N54c7c9a42d504747b857a2c38e420529
102 N3c8b457b2ba3466d93c94fda1934cae1 schema:name Springer Nature - SN SciGraph project
103 rdf:type schema:Organization
104 N5012c61986a0483fbcde296d6cc81d31 rdf:first sg:person.012727410605.86
105 rdf:rest N9dacd65a33ed4789b6574444918eadb5
106 N54c7c9a42d504747b857a2c38e420529 rdf:first N2e0c17f3405243f7bb01a0e3f70b9b18
107 rdf:rest N0f0ebe1d13034cb9a4ccb34765523743
108 N7e3e2b47162348c6a78c1bce37372126 schema:name Springer Nature
109 rdf:type schema:Organisation
110 N8ffa991b885d4ebb8590d7c6e1175fb5 schema:familyName Speckmann
111 schema:givenName Bettina
112 rdf:type schema:Person
113 N9dacd65a33ed4789b6574444918eadb5 rdf:first sg:person.015277345473.26
114 rdf:rest rdf:nil
115 Nbffc63ed9f6847129da8f3fc11460995 rdf:first N8ffa991b885d4ebb8590d7c6e1175fb5
116 rdf:rest rdf:nil
117 Nd5052c0c3e9f47b0afa2b7772ff48d64 schema:familyName Halldórsson
118 schema:givenName Magnús M.
119 rdf:type schema:Person
120 Ndb8fc587526d49fa9ccf13d76975c819 schema:name dimensions_id
121 schema:value pub.1037020507
122 rdf:type schema:PropertyValue
123 Nf26b2050e3a14e728f32c4718edeaa4c rdf:first sg:person.07522711725.87
124 rdf:rest N5012c61986a0483fbcde296d6cc81d31
125 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
126 schema:name Information and Computing Sciences
127 rdf:type schema:DefinedTerm
128 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
129 schema:name Data Format
130 rdf:type schema:DefinedTerm
131 sg:person.012727410605.86 schema:affiliation grid-institutes:grid.481551.c
132 schema:familyName Woodruff
133 schema:givenName David P.
134 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86
135 rdf:type schema:Person
136 sg:person.015277345473.26 schema:affiliation grid-institutes:grid.25879.31
137 schema:familyName Yaroslavtsev
138 schema:givenName Grigory
139 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015277345473.26
140 rdf:type schema:Person
141 sg:person.07522711725.87 schema:affiliation grid-institutes:grid.5292.c
142 schema:familyName Molinaro
143 schema:givenName Marco
144 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07522711725.87
145 rdf:type schema:Person
146 grid-institutes:grid.25879.31 schema:alternateName University of Pennsylvania, Philadelphia, PA, USA
147 schema:name University of Pennsylvania, Philadelphia, PA, USA
148 rdf:type schema:Organization
149 grid-institutes:grid.481551.c schema:alternateName IBM Almaden Research Center, San Jose, USA
150 schema:name IBM Almaden Research Center, San Jose, USA
151 rdf:type schema:Organization
152 grid-institutes:grid.5292.c schema:alternateName Delft University of Technology, Delft, The Netherlands
153 schema:name Delft University of Technology, Delft, The Netherlands
154 rdf:type schema:Organization
 




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


...