Lower Bounds on the Randomized Communication Complexity of Read-Once Functions View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2010-05-17

AUTHORS

Nikos Leonardos, Michael Saks

ABSTRACT

.We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae. A read-once boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond to variables, and the internal nodes are labeled by binary connectives. Under certain assumptions, this representation is unique. Thus, one can define the depth of a formula as the depth of the tree that represents it. The complexity of the evaluation of general read-once formulae has attracted interest mainly in the decision tree model. In the communication complexity model many interesting results deal with specific read-once formulae, such as DISJOINTNESS and TRIBES. In this paper we use information theory methods to prove lower bounds that hold for any read-once formula. Our lower bounds are of the form n(f)/cd(f), where n(f) is the number of variables and d(f) is the depth of the formula, and they are optimal up to the constant in the base of the denominator. More... »

PAGES

153-181

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00037-010-0292-2

DOI

http://dx.doi.org/10.1007/s00037-010-0292-2

DIMENSIONS

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


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/17", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology and Cognitive Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1702", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Cognitive Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Computer Science Department, Rutgers University, 110 Frelinghuysen Rd, 08854, Piscataway, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Computer Science Department, Rutgers University, 110 Frelinghuysen Rd, 08854, Piscataway, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Leonardos", 
        "givenName": "Nikos", 
        "id": "sg:person.011154751371.82", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011154751371.82"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Mathematics Department, Rutgers University, 110 Frelinghuysen Rd, 08854, Piscataway, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Mathematics Department, Rutgers University, 110 Frelinghuysen Rd, 08854, Piscataway, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saks", 
        "givenName": "Michael", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010-05-17", 
    "datePublishedReg": "2010-05-17", 
    "description": "Abstract.We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae. A read-once boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond to variables, and the internal nodes are labeled by binary connectives. Under certain assumptions, this representation is unique. Thus, one can define the depth of a formula as the depth of the tree that represents it. The complexity of the evaluation of general read-once formulae has attracted interest mainly in the decision tree model. In the communication complexity model many interesting results deal with specific read-once formulae, such as DISJOINTNESS and TRIBES. In this paper we use information theory methods to prove lower bounds that hold for any read-once formula. Our lower bounds are of the form n(f)/cd(f), where n(f) is the number of variables and d(f) is the depth of the formula, and they are optimal up to the constant in the base of the denominator.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00037-010-0292-2", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136224", 
        "issn": [
          "1016-3328", 
          "1420-8954"
        ], 
        "name": "computational complexity", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "19"
      }
    ], 
    "keywords": [
      "communication complexity", 
      "Boolean formulas", 
      "communication complexity model", 
      "information theory methods", 
      "lower bounds", 
      "two-party communication complexity", 
      "randomized communication complexity", 
      "decision tree model", 
      "complexity model", 
      "propositional logic", 
      "tree model", 
      "complexity", 
      "internal nodes", 
      "number of variables", 
      "bounds", 
      "trees", 
      "nodes", 
      "logic", 
      "disjointness", 
      "representation", 
      "interesting results", 
      "model", 
      "certain assumptions", 
      "method", 
      "base", 
      "connectives", 
      "evaluation", 
      "interest", 
      "number", 
      "function", 
      "variables", 
      "assumption", 
      "results", 
      "formula", 
      "theory method", 
      "depth", 
      "form", 
      "properties", 
      "denominator", 
      "binary connectives", 
      "constants", 
      "leaves", 
      "tribes", 
      "paper", 
      "Once Functions"
    ], 
    "name": "Lower Bounds on the Randomized Communication Complexity of Read-Once Functions", 
    "pagination": "153-181", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1047592697"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00037-010-0292-2"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00037-010-0292-2", 
      "https://app.dimensions.ai/details/publication/pub.1047592697"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-10-01T06:36", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_523.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00037-010-0292-2"
  }
]
 

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/s00037-010-0292-2'

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/s00037-010-0292-2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00037-010-0292-2'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00037-010-0292-2'


 

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

123 TRIPLES      20 PREDICATES      72 URIs      61 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00037-010-0292-2 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 anzsrc-for:0802
4 anzsrc-for:17
5 anzsrc-for:1702
6 schema:author Na7343e7a58b94e4d816ae4f36c783b3d
7 schema:datePublished 2010-05-17
8 schema:datePublishedReg 2010-05-17
9 schema:description Abstract.We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae. A read-once boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond to variables, and the internal nodes are labeled by binary connectives. Under certain assumptions, this representation is unique. Thus, one can define the depth of a formula as the depth of the tree that represents it. The complexity of the evaluation of general read-once formulae has attracted interest mainly in the decision tree model. In the communication complexity model many interesting results deal with specific read-once formulae, such as DISJOINTNESS and TRIBES. In this paper we use information theory methods to prove lower bounds that hold for any read-once formula. Our lower bounds are of the form n(f)/cd(f), where n(f) is the number of variables and d(f) is the depth of the formula, and they are optimal up to the constant in the base of the denominator.
10 schema:genre article
11 schema:isAccessibleForFree false
12 schema:isPartOf N570916c567c24fe19cdaf578f4308b04
13 Ndce1c28e87334ae58c4e28187c75d8ab
14 sg:journal.1136224
15 schema:keywords Boolean formulas
16 Once Functions
17 assumption
18 base
19 binary connectives
20 bounds
21 certain assumptions
22 communication complexity
23 communication complexity model
24 complexity
25 complexity model
26 connectives
27 constants
28 decision tree model
29 denominator
30 depth
31 disjointness
32 evaluation
33 form
34 formula
35 function
36 information theory methods
37 interest
38 interesting results
39 internal nodes
40 leaves
41 logic
42 lower bounds
43 method
44 model
45 nodes
46 number
47 number of variables
48 paper
49 properties
50 propositional logic
51 randomized communication complexity
52 representation
53 results
54 theory method
55 tree model
56 trees
57 tribes
58 two-party communication complexity
59 variables
60 schema:name Lower Bounds on the Randomized Communication Complexity of Read-Once Functions
61 schema:pagination 153-181
62 schema:productId N3afe9a8e348347c3a600d0c7962a7711
63 N815de40773a0457bb9801b11ab403089
64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047592697
65 https://doi.org/10.1007/s00037-010-0292-2
66 schema:sdDatePublished 2022-10-01T06:36
67 schema:sdLicense https://scigraph.springernature.com/explorer/license/
68 schema:sdPublisher N15c54e9af8c04ff59ce024403784799a
69 schema:url https://doi.org/10.1007/s00037-010-0292-2
70 sgo:license sg:explorer/license/
71 sgo:sdDataset articles
72 rdf:type schema:ScholarlyArticle
73 N15c54e9af8c04ff59ce024403784799a schema:name Springer Nature - SN SciGraph project
74 rdf:type schema:Organization
75 N3afe9a8e348347c3a600d0c7962a7711 schema:name doi
76 schema:value 10.1007/s00037-010-0292-2
77 rdf:type schema:PropertyValue
78 N570916c567c24fe19cdaf578f4308b04 schema:issueNumber 2
79 rdf:type schema:PublicationIssue
80 N815de40773a0457bb9801b11ab403089 schema:name dimensions_id
81 schema:value pub.1047592697
82 rdf:type schema:PropertyValue
83 N9a55f8ba565d4e7cae57e46ef297cc94 rdf:first sg:person.011520224512.05
84 rdf:rest rdf:nil
85 Na7343e7a58b94e4d816ae4f36c783b3d rdf:first sg:person.011154751371.82
86 rdf:rest N9a55f8ba565d4e7cae57e46ef297cc94
87 Ndce1c28e87334ae58c4e28187c75d8ab schema:volumeNumber 19
88 rdf:type schema:PublicationVolume
89 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
90 schema:name Information and Computing Sciences
91 rdf:type schema:DefinedTerm
92 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
93 schema:name Artificial Intelligence and Image Processing
94 rdf:type schema:DefinedTerm
95 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
96 schema:name Computation Theory and Mathematics
97 rdf:type schema:DefinedTerm
98 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
99 schema:name Psychology and Cognitive Sciences
100 rdf:type schema:DefinedTerm
101 anzsrc-for:1702 schema:inDefinedTermSet anzsrc-for:
102 schema:name Cognitive Sciences
103 rdf:type schema:DefinedTerm
104 sg:journal.1136224 schema:issn 1016-3328
105 1420-8954
106 schema:name computational complexity
107 schema:publisher Springer Nature
108 rdf:type schema:Periodical
109 sg:person.011154751371.82 schema:affiliation grid-institutes:grid.430387.b
110 schema:familyName Leonardos
111 schema:givenName Nikos
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011154751371.82
113 rdf:type schema:Person
114 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
115 schema:familyName Saks
116 schema:givenName Michael
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
118 rdf:type schema:Person
119 grid-institutes:grid.430387.b schema:alternateName Computer Science Department, Rutgers University, 110 Frelinghuysen Rd, 08854, Piscataway, NJ, USA
120 Mathematics Department, Rutgers University, 110 Frelinghuysen Rd, 08854, Piscataway, NJ, USA
121 schema:name Computer Science Department, Rutgers University, 110 Frelinghuysen Rd, 08854, Piscataway, NJ, USA
122 Mathematics Department, Rutgers University, 110 Frelinghuysen Rd, 08854, Piscataway, NJ, USA
123 rdf:type schema:Organization
 




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


...