An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2020-03-04

AUTHORS

John Chiarelli, Pooya Hatami, Michael Saks

ABSTRACT

We prove that there is a constant C ≤ 6.614 such that every Boolean function of degree at most d (as a polynomial over ℝ) is a C·2d-junta, i.e., it depends on at most C·2d variables. This improves the d·2d-1 upper bound of Nisan and Szegedy [Computational Complexity 4 (1994)].The bound of C·2d is tight up to the constant C, since a read-once decision tree of depth d depends on all 2d - 1 variables. We slightly improve this lower bound by constructing, for each positive integer d, a function of degree d with 3·2d-1 - 2 relevant variables. A similar construction was independently observed by Shinkar and Tal. More... »

PAGES

237-244

References to SciGraph publications

  • 1994-12. On the degree of boolean functions as real polynomials in COMPUTATIONAL COMPLEXITY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00493-019-4136-7

    DOI

    http://dx.doi.org/10.1007/s00493-019-4136-7

    DIMENSIONS

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


    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": "Department of Mathematics, Rutgers University, New Brunswick, USA", 
              "id": "http://www.grid.ac/institutes/grid.430387.b", 
              "name": [
                "Department of Mathematics, Rutgers University, New Brunswick, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chiarelli", 
            "givenName": "John", 
            "id": "sg:person.014533462711.16", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014533462711.16"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Engineering, Ohio State University, Columbus, USA", 
              "id": "http://www.grid.ac/institutes/grid.261331.4", 
              "name": [
                "Department of Computer Science and Engineering, Ohio State University, Columbus, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hatami", 
            "givenName": "Pooya", 
            "id": "sg:person.010120331244.54", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010120331244.54"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Mathematics, Rutgers University, New Brunswick, USA", 
              "id": "http://www.grid.ac/institutes/grid.430387.b", 
              "name": [
                "Department of Mathematics, Rutgers University, New Brunswick, 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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01263419", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019988559", 
              "https://doi.org/10.1007/bf01263419"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2020-03-04", 
        "datePublishedReg": "2020-03-04", 
        "description": "We prove that there is a constant C \u2264 6.614 such that every Boolean function of degree at most d (as a polynomial over \u211d) is a C\u00b72d-junta, i.e., it depends on at most C\u00b72d variables. This improves the d\u00b72d-1 upper bound of Nisan and Szegedy [Computational Complexity 4 (1994)].The bound of C\u00b72d is tight up to the constant C, since a read-once decision tree of depth d depends on all 2d - 1 variables. We slightly improve this lower bound by constructing, for each positive integer d, a function of degree d with 3\u00b72d-1 - 2 relevant variables. A similar construction was independently observed by Shinkar and Tal.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00493-019-4136-7", 
        "isAccessibleForFree": true, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.8832566", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1136493", 
            "issn": [
              "0209-9683", 
              "1439-6912"
            ], 
            "name": "Combinatorica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "40"
          }
        ], 
        "keywords": [
          "Boolean functions", 
          "function", 
          "variables", 
          "Nisan", 
          "Szegedy", 
          "bounds", 
          "depth d", 
          "positive integer d", 
          "integer d", 
          "degree d", 
          "relevant variables", 
          "similar construction", 
          "Shinkar", 
          "tight bounds", 
          "degree", 
          "junta", 
          "decision tree", 
          "trees", 
          "construction", 
          "TAL", 
          "number"
        ], 
        "name": "An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function", 
        "pagination": "237-244", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1125404826"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00493-019-4136-7"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00493-019-4136-7", 
          "https://app.dimensions.ai/details/publication/pub.1125404826"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-09-02T16:04", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/article/article_845.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00493-019-4136-7"
      }
    ]
     

    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-019-4136-7'

    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-019-4136-7'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-019-4136-7'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-019-4136-7'


     

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

    101 TRIPLES      21 PREDICATES      46 URIs      37 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00493-019-4136-7 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Na691039941544bd89e9f39af6db14f36
    4 schema:citation sg:pub.10.1007/bf01263419
    5 schema:datePublished 2020-03-04
    6 schema:datePublishedReg 2020-03-04
    7 schema:description We prove that there is a constant C ≤ 6.614 such that every Boolean function of degree at most d (as a polynomial over ℝ) is a C·2d-junta, i.e., it depends on at most C·2d variables. This improves the d·2d-1 upper bound of Nisan and Szegedy [Computational Complexity 4 (1994)].The bound of C·2d is tight up to the constant C, since a read-once decision tree of depth d depends on all 2d - 1 variables. We slightly improve this lower bound by constructing, for each positive integer d, a function of degree d with 3·2d-1 - 2 relevant variables. A similar construction was independently observed by Shinkar and Tal.
    8 schema:genre article
    9 schema:isAccessibleForFree true
    10 schema:isPartOf N53b2d8e09e0547829fb054e45e5c8115
    11 N85bfc77a92004d9092d10987ee97660a
    12 sg:journal.1136493
    13 schema:keywords Boolean functions
    14 Nisan
    15 Shinkar
    16 Szegedy
    17 TAL
    18 bounds
    19 construction
    20 decision tree
    21 degree
    22 degree d
    23 depth d
    24 function
    25 integer d
    26 junta
    27 number
    28 positive integer d
    29 relevant variables
    30 similar construction
    31 tight bounds
    32 trees
    33 variables
    34 schema:name An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function
    35 schema:pagination 237-244
    36 schema:productId N094bd3e6704d4e8e975bc5b7dd6fa424
    37 N59078403658b49f6aed2abc6254245b9
    38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1125404826
    39 https://doi.org/10.1007/s00493-019-4136-7
    40 schema:sdDatePublished 2022-09-02T16:04
    41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    42 schema:sdPublisher Nf3dc4bc72c024297bc636a3189b4f941
    43 schema:url https://doi.org/10.1007/s00493-019-4136-7
    44 sgo:license sg:explorer/license/
    45 sgo:sdDataset articles
    46 rdf:type schema:ScholarlyArticle
    47 N094bd3e6704d4e8e975bc5b7dd6fa424 schema:name dimensions_id
    48 schema:value pub.1125404826
    49 rdf:type schema:PropertyValue
    50 N23d67aa262fb4778ba39c331b60345be rdf:first sg:person.010120331244.54
    51 rdf:rest N5600ddc090d645f1817c996e4a615de1
    52 N53b2d8e09e0547829fb054e45e5c8115 schema:volumeNumber 40
    53 rdf:type schema:PublicationVolume
    54 N5600ddc090d645f1817c996e4a615de1 rdf:first sg:person.011520224512.05
    55 rdf:rest rdf:nil
    56 N59078403658b49f6aed2abc6254245b9 schema:name doi
    57 schema:value 10.1007/s00493-019-4136-7
    58 rdf:type schema:PropertyValue
    59 N85bfc77a92004d9092d10987ee97660a schema:issueNumber 2
    60 rdf:type schema:PublicationIssue
    61 Na691039941544bd89e9f39af6db14f36 rdf:first sg:person.014533462711.16
    62 rdf:rest N23d67aa262fb4778ba39c331b60345be
    63 Nf3dc4bc72c024297bc636a3189b4f941 schema:name Springer Nature - SN SciGraph project
    64 rdf:type schema:Organization
    65 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Mathematical Sciences
    67 rdf:type schema:DefinedTerm
    68 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Pure Mathematics
    70 rdf:type schema:DefinedTerm
    71 sg:grant.8832566 http://pending.schema.org/fundedItem sg:pub.10.1007/s00493-019-4136-7
    72 rdf:type schema:MonetaryGrant
    73 sg:journal.1136493 schema:issn 0209-9683
    74 1439-6912
    75 schema:name Combinatorica
    76 schema:publisher Springer Nature
    77 rdf:type schema:Periodical
    78 sg:person.010120331244.54 schema:affiliation grid-institutes:grid.261331.4
    79 schema:familyName Hatami
    80 schema:givenName Pooya
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010120331244.54
    82 rdf:type schema:Person
    83 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
    84 schema:familyName Saks
    85 schema:givenName Michael
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
    87 rdf:type schema:Person
    88 sg:person.014533462711.16 schema:affiliation grid-institutes:grid.430387.b
    89 schema:familyName Chiarelli
    90 schema:givenName John
    91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014533462711.16
    92 rdf:type schema:Person
    93 sg:pub.10.1007/bf01263419 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019988559
    94 https://doi.org/10.1007/bf01263419
    95 rdf:type schema:CreativeWork
    96 grid-institutes:grid.261331.4 schema:alternateName Department of Computer Science and Engineering, Ohio State University, Columbus, USA
    97 schema:name Department of Computer Science and Engineering, Ohio State University, Columbus, USA
    98 rdf:type schema:Organization
    99 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers University, New Brunswick, USA
    100 schema:name Department of Mathematics, Rutgers University, New Brunswick, USA
    101 rdf:type schema:Organization
     




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


    ...