On the Fourier spectrum of symmetric Boolean functions View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2009-05

AUTHORS

Mihail N. Kolountzakis, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth K. Vishnoi

ABSTRACT

We study the following questionWhat is the smallest t such that every symmetric boolean function on κ variables (which is not a constant or a parity function), has a non-zero Fourier coefficient of order at least 1 and at most t?We exclude the constant functions for which there is no such t and the parity functions for which t has to be κ. Let τ (κ) be the smallest such t. Our main result is that for large κ, τ (κ)≤4κ/logκ.The motivation for our work is to understand the complexity of learning symmetric juntas. A κ-junta is a boolean function of n variables that depends only on an unknown subset of κ variables. A symmetric κ-junta is a junta that is symmetric in the variables it depends on. Our result implies an algorithm to learn the class of symmetric κ-juntas, in the uniform PAC learning model, in time no(κ). This improves on a result of Mossel, O’Donnell and Servedio in [16], who show that symmetric κ-juntas can be learned in time n2κ/3. More... »

PAGES

363-387

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00493-009-2310-z

DOI

http://dx.doi.org/10.1007/s00493-009-2310-z

DIMENSIONS

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


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, Univ. of Crete, GR-71409, Iraklio, Greece", 
          "id": "http://www.grid.ac/institutes/grid.8127.c", 
          "name": [
            "Department of Mathematics, Univ. of Crete, GR-71409, Iraklio, Greece"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kolountzakis", 
        "givenName": "Mihail N.", 
        "id": "sg:person.014010763055.75", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014010763055.75"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Telcordia Research, 07960, Morristown, NJ, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Georgia Tech, College of Computing, Atlanta, GA 30332, USA", 
            "Telcordia Research, 07960, Morristown, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lipton", 
        "givenName": "Richard J.", 
        "id": "sg:person.010133373171.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010133373171.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Centre for Math and Computer Science (CWI), Kruislaan 413, Amsterdam, The Netherlands", 
          "id": "http://www.grid.ac/institutes/grid.6054.7", 
          "name": [
            "Centre for Math and Computer Science (CWI), Kruislaan 413, Amsterdam, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Markakis", 
        "givenName": "Evangelos", 
        "id": "sg:person.014013771241.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014013771241.29"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Almaden Research Center, 650 Harry Rd, 95120, San Jose, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.481551.c", 
          "name": [
            "IBM Almaden Research Center, 650 Harry Rd, 95120, San Jose, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehta", 
        "givenName": "Aranyak", 
        "id": "sg:person.010106546671.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010106546671.08"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM India Research Lab, Block-1, IIT Delhi, 110016, New Delhi, India", 
          "id": "http://www.grid.ac/institutes/grid.417967.a", 
          "name": [
            "College of Computing, Georgia Institute of Technology, 30332, Atlanta, GA, USA", 
            "IBM India Research Lab, Block-1, IIT Delhi, 110016, New Delhi, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vishnoi", 
        "givenName": "Nisheeth K.", 
        "id": "sg:person.011753303543.94", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011753303543.94"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-48329-2_24", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045214757", 
          "https://doi.org/10.1007/3-540-48329-2_24"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-49730-7_27", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000045511", 
          "https://doi.org/10.1007/3-540-49730-7_27"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4757-6292-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032334456", 
          "https://doi.org/10.1007/978-1-4757-6292-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01215917", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050270206", 
          "https://doi.org/10.1007/bf01215917"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2009-05", 
    "datePublishedReg": "2009-05-01", 
    "description": "We study the following questionWhat is the smallest t such that every symmetric boolean function on \u03ba variables (which is not a constant or a parity function), has a non-zero Fourier coefficient of order at least 1 and at most t?We exclude the constant functions for which there is no such t and the parity functions for which t has to be \u03ba. Let \u03c4 (\u03ba) be the smallest such t. Our main result is that for large \u03ba, \u03c4 (\u03ba)\u22644\u03ba/log\u03ba.The motivation for our work is to understand the complexity of learning symmetric juntas. A \u03ba-junta is a boolean function of n variables that depends only on an unknown subset of \u03ba variables. A symmetric \u03ba-junta is a junta that is symmetric in the variables it depends on. Our result implies an algorithm to learn the class of symmetric \u03ba-juntas, in the uniform PAC learning model, in time no(\u03ba). This improves on a result of Mossel, O\u2019Donnell and Servedio in [16], who show that symmetric \u03ba-juntas can be learned in time n2\u03ba/3.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00493-009-2310-z", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136493", 
        "issn": [
          "0209-9683", 
          "1439-6912"
        ], 
        "name": "Combinatorica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "29"
      }
    ], 
    "keywords": [
      "function", 
      "main results", 
      "variables", 
      "results", 
      "subset", 
      "time", 
      "class", 
      "model", 
      "order", 
      "motivation", 
      "coefficient", 
      "work", 
      "complexity", 
      "unknown subset", 
      "learning model", 
      "spectra", 
      "symmetric Boolean functions", 
      "parity function", 
      "Boolean functions", 
      "Fourier coefficients", 
      "algorithm", 
      "PAC learning model", 
      "constant function", 
      "junta", 
      "Mossel", 
      "O\u2019Donnell", 
      "Fourier spectrum", 
      "Servedio"
    ], 
    "name": "On the Fourier spectrum of symmetric Boolean functions", 
    "pagination": "363-387", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1032741467"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00493-009-2310-z"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00493-009-2310-z", 
      "https://app.dimensions.ai/details/publication/pub.1032741467"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-05-20T07:25", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_487.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00493-009-2310-z"
  }
]
 

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-009-2310-z'

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-009-2310-z'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-009-2310-z'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-009-2310-z'


 

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

144 TRIPLES      22 PREDICATES      58 URIs      46 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00493-009-2310-z schema:about anzsrc-for:01
2 anzsrc-for:08
3 schema:author Nb2f0e4fdc78a4065b6db4af177ac9093
4 schema:citation sg:pub.10.1007/3-540-48329-2_24
5 sg:pub.10.1007/3-540-49730-7_27
6 sg:pub.10.1007/978-1-4757-6292-1
7 sg:pub.10.1007/bf01215917
8 schema:datePublished 2009-05
9 schema:datePublishedReg 2009-05-01
10 schema:description We study the following questionWhat is the smallest t such that every symmetric boolean function on κ variables (which is not a constant or a parity function), has a non-zero Fourier coefficient of order at least 1 and at most t?We exclude the constant functions for which there is no such t and the parity functions for which t has to be κ. Let τ (κ) be the smallest such t. Our main result is that for large κ, τ (κ)≤4κ/logκ.The motivation for our work is to understand the complexity of learning symmetric juntas. A κ-junta is a boolean function of n variables that depends only on an unknown subset of κ variables. A symmetric κ-junta is a junta that is symmetric in the variables it depends on. Our result implies an algorithm to learn the class of symmetric κ-juntas, in the uniform PAC learning model, in time no(κ). This improves on a result of Mossel, O’Donnell and Servedio in [16], who show that symmetric κ-juntas can be learned in time n2κ/3.
11 schema:genre article
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf N88ea5d7deff4487fa65ea7805e7ccdf4
15 Na1795f463896402299b6cc74fc2f7475
16 sg:journal.1136493
17 schema:keywords Boolean functions
18 Fourier coefficients
19 Fourier spectrum
20 Mossel
21 O’Donnell
22 PAC learning model
23 Servedio
24 algorithm
25 class
26 coefficient
27 complexity
28 constant function
29 function
30 junta
31 learning model
32 main results
33 model
34 motivation
35 order
36 parity function
37 results
38 spectra
39 subset
40 symmetric Boolean functions
41 time
42 unknown subset
43 variables
44 work
45 schema:name On the Fourier spectrum of symmetric Boolean functions
46 schema:pagination 363-387
47 schema:productId N0984602704c3434fb61ec57ce914e87b
48 N36d87c06612f484680119f9fd1e2df17
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032741467
50 https://doi.org/10.1007/s00493-009-2310-z
51 schema:sdDatePublished 2022-05-20T07:25
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher Nbb21c25dea76436c857b971e15cb8c79
54 schema:url https://doi.org/10.1007/s00493-009-2310-z
55 sgo:license sg:explorer/license/
56 sgo:sdDataset articles
57 rdf:type schema:ScholarlyArticle
58 N05feb845280d44f0bc209e08b7bc955a rdf:first sg:person.010106546671.08
59 rdf:rest Ndaae97df85c9485ebf57430d56322f23
60 N0984602704c3434fb61ec57ce914e87b schema:name dimensions_id
61 schema:value pub.1032741467
62 rdf:type schema:PropertyValue
63 N36d87c06612f484680119f9fd1e2df17 schema:name doi
64 schema:value 10.1007/s00493-009-2310-z
65 rdf:type schema:PropertyValue
66 N4ee1321aaf0f4400b6b3739c756758da rdf:first sg:person.010133373171.27
67 rdf:rest Nfa9cff3369d44b76877866ed9c9b98d1
68 N88ea5d7deff4487fa65ea7805e7ccdf4 schema:volumeNumber 29
69 rdf:type schema:PublicationVolume
70 Na1795f463896402299b6cc74fc2f7475 schema:issueNumber 3
71 rdf:type schema:PublicationIssue
72 Nb2f0e4fdc78a4065b6db4af177ac9093 rdf:first sg:person.014010763055.75
73 rdf:rest N4ee1321aaf0f4400b6b3739c756758da
74 Nbb21c25dea76436c857b971e15cb8c79 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 Ndaae97df85c9485ebf57430d56322f23 rdf:first sg:person.011753303543.94
77 rdf:rest rdf:nil
78 Nfa9cff3369d44b76877866ed9c9b98d1 rdf:first sg:person.014013771241.29
79 rdf:rest N05feb845280d44f0bc209e08b7bc955a
80 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
81 schema:name Mathematical Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
84 schema:name Information and Computing Sciences
85 rdf:type schema:DefinedTerm
86 sg:journal.1136493 schema:issn 0209-9683
87 1439-6912
88 schema:name Combinatorica
89 schema:publisher Springer Nature
90 rdf:type schema:Periodical
91 sg:person.010106546671.08 schema:affiliation grid-institutes:grid.481551.c
92 schema:familyName Mehta
93 schema:givenName Aranyak
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010106546671.08
95 rdf:type schema:Person
96 sg:person.010133373171.27 schema:affiliation grid-institutes:None
97 schema:familyName Lipton
98 schema:givenName Richard J.
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010133373171.27
100 rdf:type schema:Person
101 sg:person.011753303543.94 schema:affiliation grid-institutes:grid.417967.a
102 schema:familyName Vishnoi
103 schema:givenName Nisheeth K.
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011753303543.94
105 rdf:type schema:Person
106 sg:person.014010763055.75 schema:affiliation grid-institutes:grid.8127.c
107 schema:familyName Kolountzakis
108 schema:givenName Mihail N.
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014010763055.75
110 rdf:type schema:Person
111 sg:person.014013771241.29 schema:affiliation grid-institutes:grid.6054.7
112 schema:familyName Markakis
113 schema:givenName Evangelos
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014013771241.29
115 rdf:type schema:Person
116 sg:pub.10.1007/3-540-48329-2_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045214757
117 https://doi.org/10.1007/3-540-48329-2_24
118 rdf:type schema:CreativeWork
119 sg:pub.10.1007/3-540-49730-7_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000045511
120 https://doi.org/10.1007/3-540-49730-7_27
121 rdf:type schema:CreativeWork
122 sg:pub.10.1007/978-1-4757-6292-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032334456
123 https://doi.org/10.1007/978-1-4757-6292-1
124 rdf:type schema:CreativeWork
125 sg:pub.10.1007/bf01215917 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050270206
126 https://doi.org/10.1007/bf01215917
127 rdf:type schema:CreativeWork
128 grid-institutes:None schema:alternateName Telcordia Research, 07960, Morristown, NJ, USA
129 schema:name Georgia Tech, College of Computing, Atlanta, GA 30332, USA
130 Telcordia Research, 07960, Morristown, NJ, USA
131 rdf:type schema:Organization
132 grid-institutes:grid.417967.a schema:alternateName IBM India Research Lab, Block-1, IIT Delhi, 110016, New Delhi, India
133 schema:name College of Computing, Georgia Institute of Technology, 30332, Atlanta, GA, USA
134 IBM India Research Lab, Block-1, IIT Delhi, 110016, New Delhi, India
135 rdf:type schema:Organization
136 grid-institutes:grid.481551.c schema:alternateName IBM Almaden Research Center, 650 Harry Rd, 95120, San Jose, CA, USA
137 schema:name IBM Almaden Research Center, 650 Harry Rd, 95120, San Jose, CA, USA
138 rdf:type schema:Organization
139 grid-institutes:grid.6054.7 schema:alternateName Centre for Math and Computer Science (CWI), Kruislaan 413, Amsterdam, The Netherlands
140 schema:name Centre for Math and Computer Science (CWI), Kruislaan 413, Amsterdam, The Netherlands
141 rdf:type schema:Organization
142 grid-institutes:grid.8127.c schema:alternateName Department of Mathematics, Univ. of Crete, GR-71409, Iraklio, Greece
143 schema:name Department of Mathematics, Univ. of Crete, GR-71409, Iraklio, Greece
144 rdf:type schema:Organization
 




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


...