The fourier entropy-influence conjecture for certain classes of Boolean functions

Ryan O'Donnell, John Wright, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In 1996, Friedgut and Kalai made the Fourier Entropy- Influence Conjecture: For every Boolean function it holds that , where is the spectral entropy of f, I[f] is the total influence of f, and C is a universal constant. In this work we verify the conjecture for symmetric functions. More generally, we verify it for functions with symmetry group where d is constant. We also verify the conjecture for functions computable by read-once decision trees.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings
Pages330-341
Number of pages12
EditionPART 1
DOIs
StatePublished - Jul 11 2011
Externally publishedYes
Event38th International Colloquium on Automata, Languages and Programming, ICALP 2011 - Zurich, Switzerland
Duration: Jul 4 2011Jul 8 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume6755 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other38th International Colloquium on Automata, Languages and Programming, ICALP 2011
CountrySwitzerland
CityZurich
Period7/4/117/8/11

Fingerprint

Boolean functions
Boolean Functions
Entropy
Verify
Symmetric Functions
Decision trees
Symmetry Group
Decision tree
Class
Influence

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

O'Donnell, R., Wright, J., & Zhou, Y. (2011). The fourier entropy-influence conjecture for certain classes of Boolean functions. In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings (PART 1 ed., pp. 330-341). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6755 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-22006-7_28

The fourier entropy-influence conjecture for certain classes of Boolean functions. / O'Donnell, Ryan; Wright, John; Zhou, Yuan.

Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. PART 1. ed. 2011. p. 330-341 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6755 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

O'Donnell, R, Wright, J & Zhou, Y 2011, The fourier entropy-influence conjecture for certain classes of Boolean functions. in Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 6755 LNCS, pp. 330-341, 38th International Colloquium on Automata, Languages and Programming, ICALP 2011, Zurich, Switzerland, 7/4/11. https://doi.org/10.1007/978-3-642-22006-7_28
O'Donnell R, Wright J, Zhou Y. The fourier entropy-influence conjecture for certain classes of Boolean functions. In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. PART 1 ed. 2011. p. 330-341. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). https://doi.org/10.1007/978-3-642-22006-7_28
O'Donnell, Ryan ; Wright, John ; Zhou, Yuan. / The fourier entropy-influence conjecture for certain classes of Boolean functions. Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. PART 1. ed. 2011. pp. 330-341 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).
@inproceedings{f8e47257e4b743d4b8e8455ff8064c75,
title = "The fourier entropy-influence conjecture for certain classes of Boolean functions",
abstract = "In 1996, Friedgut and Kalai made the Fourier Entropy- Influence Conjecture: For every Boolean function it holds that , where is the spectral entropy of f, I[f] is the total influence of f, and C is a universal constant. In this work we verify the conjecture for symmetric functions. More generally, we verify it for functions with symmetry group where d is constant. We also verify the conjecture for functions computable by read-once decision trees.",
author = "Ryan O'Donnell and John Wright and Yuan Zhou",
year = "2011",
month = "7",
day = "11",
doi = "10.1007/978-3-642-22006-7_28",
language = "English (US)",
isbn = "9783642220050",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
number = "PART 1",
pages = "330--341",
booktitle = "Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings",
edition = "PART 1",

}

TY - GEN

T1 - The fourier entropy-influence conjecture for certain classes of Boolean functions

AU - O'Donnell, Ryan

AU - Wright, John

AU - Zhou, Yuan

PY - 2011/7/11

Y1 - 2011/7/11

N2 - In 1996, Friedgut and Kalai made the Fourier Entropy- Influence Conjecture: For every Boolean function it holds that , where is the spectral entropy of f, I[f] is the total influence of f, and C is a universal constant. In this work we verify the conjecture for symmetric functions. More generally, we verify it for functions with symmetry group where d is constant. We also verify the conjecture for functions computable by read-once decision trees.

AB - In 1996, Friedgut and Kalai made the Fourier Entropy- Influence Conjecture: For every Boolean function it holds that , where is the spectral entropy of f, I[f] is the total influence of f, and C is a universal constant. In this work we verify the conjecture for symmetric functions. More generally, we verify it for functions with symmetry group where d is constant. We also verify the conjecture for functions computable by read-once decision trees.

UR - http://www.scopus.com/inward/record.url?scp=79959978489&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79959978489&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-22006-7_28

DO - 10.1007/978-3-642-22006-7_28

M3 - Conference contribution

AN - SCOPUS:79959978489

SN - 9783642220050

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 330

EP - 341

BT - Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings

ER -