Composition limits and separating examples for some boolean function complexity measures View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2016-01-11

AUTHORS

Justin Gilmer, Michael Saks, Srikanth Srinivasan

ABSTRACT

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... »

PAGES

265-311

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/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

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/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
 




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


...