Ontology type: schema:ScholarlyArticle Open Access: True

2016-01-11

Justin Gilmer, Michael Saks, Srikanth Srinivasan

Block sensitivity (bs(f)), certificate complexity (C(f)) and fractional certificate complexity (C*(f)) are three fundamental combinatorial measures of complexity of a boolean function f. It has long been known that bs(f) ≤ C*(f) ≤ C(f) = O(bs(f)2). We provide an infinite family of examples for which C(f) grows quadratically in C*(f) (and also bs(f)) giving optimal separations between these measures. Previously the biggest separation known was \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(f) = C*(f)^{\log _{4,5} 5}$$\end{document}. We also give a family of examples for which C*(f)= Ω (bs(f)3/2).These examples are obtained by composing boolean functions in various ways. Here the composition fog of f with g is obtained by substituting for each variable of f a copy of g on disjoint sets of variables. To construct and analyse these examples we systematically investigate the behaviour under function composition of these measures and also the sensitivity measure s(f). The measures s(f), C(f) and C*(f) behave nicely under composition: they are submultiplicative (where measure m is submultiplicative if m(fog) ≤ m(f)m(g)) with equality holding under some fairly general conditions. The measure bs(f) is qualitatively different: it is not submultiplicative. This qualitative difference was not noticed in the previous literature and we correct some errors that appeared in previous papers. We define the composition limit of a measure m at function f, mlim(f) to be the limit as k grows of m(f(k))1/k, where f(k) is the iterated composition of f with itself k-times. For any function f we show that bslim(f) = (C*)lim(f) and characterize slim(f); (C*)lim(f), and Clim(f) in terms of the largest eigenvalue of a certain set of 2×2 matrices associated with f. More... »

265-311

http://scigraph.springernature.com/pub.10.1007/s00493-014-3189-x

http://dx.doi.org/10.1007/s00493-014-3189-x

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

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/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Mathematics, Rutgers University, Piscataway, NJ, USA",
"id": "http://www.grid.ac/institutes/grid.430387.b",
"name": [
"Department of Mathematics, Rutgers University, Piscataway, NJ, USA"
],
"type": "Organization"
},
"familyName": "Gilmer",
"givenName": "Justin",
"id": "sg:person.014071223267.11",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014071223267.11"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Mathematics, Rutgers University, Piscataway, NJ, USA",
"id": "http://www.grid.ac/institutes/grid.430387.b",
"name": [
"Department of Mathematics, Rutgers University, 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"
},
{
"affiliation": {
"alternateName": "Department of Mathematics, IIT Bombay, Mumbai, India",
"id": "http://www.grid.ac/institutes/grid.417971.d",
"name": [
"Department of Mathematics, IIT Bombay, Mumbai, India"
],
"type": "Organization"
},
"familyName": "Srinivasan",
"givenName": "Srikanth",
"id": "sg:person.011304215743.14",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011304215743.14"
],
"type": "Person"
}
],
"datePublished": "2016-01-11",
"datePublishedReg": "2016-01-11",
"description": "Block sensitivity (bs(f)), certificate complexity (C(f)) and fractional certificate complexity (C*(f)) are three fundamental combinatorial measures of complexity of a boolean function f. It has long been known that bs(f) \u2264 C*(f) \u2264 C(f) = O(bs(f)2). We provide an infinite family of examples for which C(f) grows quadratically in C*(f) (and also bs(f)) giving optimal separations between these measures. Previously the biggest separation known was \\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}$$C(f) = C*(f)^{\\log _{4,5} 5}$$\\end{document}. We also give a family of examples for which C*(f)= \u03a9 (bs(f)3/2).These examples are obtained by composing boolean functions in various ways. Here the composition fog of f with g is obtained by substituting for each variable of f a copy of g on disjoint sets of variables. To construct and analyse these examples we systematically investigate the behaviour under function composition of these measures and also the sensitivity measure s(f). The measures s(f), C(f) and C*(f) behave nicely under composition: they are submultiplicative (where measure m is submultiplicative if m(fog) \u2264 m(f)m(g)) with equality holding under some fairly general conditions. The measure bs(f) is qualitatively different: it is not submultiplicative. This qualitative difference was not noticed in the previous literature and we correct some errors that appeared in previous papers. We define the composition limit of a measure m at function f, mlim(f) to be the limit as k grows of m(f(k))1/k, where f(k) is the iterated composition of f with itself k-times. For any function f we show that bslim(f) = (C*)lim(f) and characterize slim(f); (C*)lim(f), and Clim(f) in terms of the largest eigenvalue of a certain set of 2\u00d72 matrices associated with f.",
"genre": "article",
"id": "sg:pub.10.1007/s00493-014-3189-x",
"isAccessibleForFree": true,
"isPartOf": [
{
"id": "sg:journal.1136493",
"issn": [
"0209-9683",
"1439-6912"
],
"name": "Combinatorica",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "3",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "36"
}
],
"keywords": [
"family of examples",
"certificate complexity",
"infinite family",
"function f",
"iterated composition",
"largest eigenvalue",
"block sensitivity",
"complexity",
"combinatorial measures",
"Boolean function f.",
"function f.",
"big separation",
"Boolean functions",
"disjoint sets",
"function composition",
"sensitivity measures",
"previous paper",
"k times",
"certain set",
"complexity measures",
"example",
"fog",
"set",
"general condition",
"limit",
"eigenvalues",
"function",
"way",
"variables",
"qualitative differences",
"previous literature",
"error",
"composition limits",
"grows",
"terms",
"matrix",
"measures",
"family",
"optimal separation",
"copies",
"behavior",
"equality",
"conditions",
"sensitivity",
"f.",
"separation",
"composition",
"literature",
"differences",
"paper"
],
"name": "Composition limits and separating examples for some boolean function complexity measures",
"pagination": "265-311",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1014710224"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00493-014-3189-x"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00493-014-3189-x",
"https://app.dimensions.ai/details/publication/pub.1014710224"
],
"sdDataset": "articles",
"sdDatePublished": "2022-10-01T06:42",
"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_704.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00493-014-3189-x"
}
]
```

Download the RDF metadata as: json-ld nt turtle xml License info

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/s00493-014-3189-x'

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/s00493-014-3189-x'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-014-3189-x'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-014-3189-x'

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

124 TRIPLES
20 PREDICATES
74 URIs
66 LITERALS
6 BLANK NODES

Subject | Predicate | Object | |
---|---|---|---|

1 | sg:pub.10.1007/s00493-014-3189-x | schema:about | anzsrc-for:01 |

2 | ″ | ″ | anzsrc-for:08 |

3 | ″ | schema:author | N9aa8e55656f041e8b09358125dacc77e |

4 | ″ | schema:datePublished | 2016-01-11 |

5 | ″ | schema:datePublishedReg | 2016-01-11 |

6 | ″ | schema:description | Block sensitivity (bs(f)), certificate complexity (C(f)) and fractional certificate complexity (C*(f)) are three fundamental combinatorial measures of complexity of a boolean function f. It has long been known that bs(f) ≤ C*(f) ≤ C(f) = O(bs(f)2). We provide an infinite family of examples for which C(f) grows quadratically in C*(f) (and also bs(f)) giving optimal separations between these measures. Previously the biggest separation known was \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(f) = C*(f)^{\log _{4,5} 5}$$\end{document}. We also give a family of examples for which C*(f)= Ω (bs(f)3/2).These examples are obtained by composing boolean functions in various ways. Here the composition fog of f with g is obtained by substituting for each variable of f a copy of g on disjoint sets of variables. To construct and analyse these examples we systematically investigate the behaviour under function composition of these measures and also the sensitivity measure s(f). The measures s(f), C(f) and C*(f) behave nicely under composition: they are submultiplicative (where measure m is submultiplicative if m(fog) ≤ m(f)m(g)) with equality holding under some fairly general conditions. The measure bs(f) is qualitatively different: it is not submultiplicative. This qualitative difference was not noticed in the previous literature and we correct some errors that appeared in previous papers. We define the composition limit of a measure m at function f, mlim(f) to be the limit as k grows of m(f(k))1/k, where f(k) is the iterated composition of f with itself k-times. For any function f we show that bslim(f) = (C*)lim(f) and characterize slim(f); (C*)lim(f), and Clim(f) in terms of the largest eigenvalue of a certain set of 2×2 matrices associated with f. |

7 | ″ | schema:genre | article |

8 | ″ | schema:isAccessibleForFree | true |

9 | ″ | schema:isPartOf | Nb4148e47863443c6bb87edf1cff5a917 |

10 | ″ | ″ | Nb71f0bc4beef420bbe4474dc3d9a860c |

11 | ″ | ″ | sg:journal.1136493 |

12 | ″ | schema:keywords | Boolean function f. |

13 | ″ | ″ | Boolean functions |

14 | ″ | ″ | behavior |

15 | ″ | ″ | big separation |

16 | ″ | ″ | block sensitivity |

17 | ″ | ″ | certain set |

18 | ″ | ″ | certificate complexity |

19 | ″ | ″ | combinatorial measures |

20 | ″ | ″ | complexity |

21 | ″ | ″ | complexity measures |

22 | ″ | ″ | composition |

23 | ″ | ″ | composition limits |

24 | ″ | ″ | conditions |

25 | ″ | ″ | copies |

26 | ″ | ″ | differences |

27 | ″ | ″ | disjoint sets |

28 | ″ | ″ | eigenvalues |

29 | ″ | ″ | equality |

30 | ″ | ″ | error |

31 | ″ | ″ | example |

32 | ″ | ″ | f. |

33 | ″ | ″ | family |

34 | ″ | ″ | family of examples |

35 | ″ | ″ | fog |

36 | ″ | ″ | function |

37 | ″ | ″ | function composition |

38 | ″ | ″ | function f |

39 | ″ | ″ | function f. |

40 | ″ | ″ | general condition |

41 | ″ | ″ | grows |

42 | ″ | ″ | infinite family |

43 | ″ | ″ | iterated composition |

44 | ″ | ″ | k times |

45 | ″ | ″ | largest eigenvalue |

46 | ″ | ″ | limit |

47 | ″ | ″ | literature |

48 | ″ | ″ | matrix |

49 | ″ | ″ | measures |

50 | ″ | ″ | optimal separation |

51 | ″ | ″ | paper |

52 | ″ | ″ | previous literature |

53 | ″ | ″ | previous paper |

54 | ″ | ″ | qualitative differences |

55 | ″ | ″ | sensitivity |

56 | ″ | ″ | sensitivity measures |

57 | ″ | ″ | separation |

58 | ″ | ″ | set |

59 | ″ | ″ | terms |

60 | ″ | ″ | variables |

61 | ″ | ″ | way |

62 | ″ | schema:name | Composition limits and separating examples for some boolean function complexity measures |

63 | ″ | schema:pagination | 265-311 |

64 | ″ | schema:productId | N1e5f80df5e8247b0b4b1e61ce5cf17cb |

65 | ″ | ″ | N37122a75f0db461c9d4548a4c9b8741d |

66 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1014710224 |

67 | ″ | ″ | https://doi.org/10.1007/s00493-014-3189-x |

68 | ″ | schema:sdDatePublished | 2022-10-01T06:42 |

69 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |

70 | ″ | schema:sdPublisher | N28da11dbe2544691b72d52dc98ee3058 |

71 | ″ | schema:url | https://doi.org/10.1007/s00493-014-3189-x |

72 | ″ | sgo:license | sg:explorer/license/ |

73 | ″ | sgo:sdDataset | articles |

74 | ″ | rdf:type | schema:ScholarlyArticle |

75 | N1e5f80df5e8247b0b4b1e61ce5cf17cb | schema:name | doi |

76 | ″ | schema:value | 10.1007/s00493-014-3189-x |

77 | ″ | rdf:type | schema:PropertyValue |

78 | N28da11dbe2544691b72d52dc98ee3058 | schema:name | Springer Nature - SN SciGraph project |

79 | ″ | rdf:type | schema:Organization |

80 | N37122a75f0db461c9d4548a4c9b8741d | schema:name | dimensions_id |

81 | ″ | schema:value | pub.1014710224 |

82 | ″ | rdf:type | schema:PropertyValue |

83 | N92ded70af04143e6a5c6f0fd7c7eda9a | rdf:first | sg:person.011520224512.05 |

84 | ″ | rdf:rest | Nb9ccfa8c0ef944658c3ce0f952bbe228 |

85 | N9aa8e55656f041e8b09358125dacc77e | rdf:first | sg:person.014071223267.11 |

86 | ″ | rdf:rest | N92ded70af04143e6a5c6f0fd7c7eda9a |

87 | Nb4148e47863443c6bb87edf1cff5a917 | schema:volumeNumber | 36 |

88 | ″ | rdf:type | schema:PublicationVolume |

89 | Nb71f0bc4beef420bbe4474dc3d9a860c | schema:issueNumber | 3 |

90 | ″ | rdf:type | schema:PublicationIssue |

91 | Nb9ccfa8c0ef944658c3ce0f952bbe228 | rdf:first | sg:person.011304215743.14 |

92 | ″ | rdf:rest | rdf:nil |

93 | anzsrc-for:01 | schema:inDefinedTermSet | anzsrc-for: |

94 | ″ | schema:name | Mathematical Sciences |

95 | ″ | rdf:type | schema:DefinedTerm |

96 | anzsrc-for:08 | schema:inDefinedTermSet | anzsrc-for: |

97 | ″ | schema:name | Information and Computing Sciences |

98 | ″ | rdf:type | schema:DefinedTerm |

99 | sg:journal.1136493 | schema:issn | 0209-9683 |

100 | ″ | ″ | 1439-6912 |

101 | ″ | schema:name | Combinatorica |

102 | ″ | schema:publisher | Springer Nature |

103 | ″ | rdf:type | schema:Periodical |

104 | sg:person.011304215743.14 | schema:affiliation | grid-institutes:grid.417971.d |

105 | ″ | schema:familyName | Srinivasan |

106 | ″ | schema:givenName | Srikanth |

107 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011304215743.14 |

108 | ″ | rdf:type | schema:Person |

109 | sg:person.011520224512.05 | schema:affiliation | grid-institutes:grid.430387.b |

110 | ″ | schema:familyName | Saks |

111 | ″ | schema:givenName | Michael |

112 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05 |

113 | ″ | rdf:type | schema:Person |

114 | sg:person.014071223267.11 | schema:affiliation | grid-institutes:grid.430387.b |

115 | ″ | schema:familyName | Gilmer |

116 | ″ | schema:givenName | Justin |

117 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014071223267.11 |

118 | ″ | rdf:type | schema:Person |

119 | grid-institutes:grid.417971.d | schema:alternateName | Department of Mathematics, IIT Bombay, Mumbai, India |

120 | ″ | schema:name | Department of Mathematics, IIT Bombay, Mumbai, India |

121 | ″ | rdf:type | schema:Organization |

122 | grid-institutes:grid.430387.b | schema:alternateName | Department of Mathematics, Rutgers University, Piscataway, NJ, USA |

123 | ″ | schema:name | Department of Mathematics, Rutgers University, Piscataway, NJ, USA |

124 | ″ | rdf:type | schema:Organization |