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
Country/TerritorySwitzerland
CityZurich
Period7/4/117/8/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'The fourier entropy-influence conjecture for certain classes of Boolean functions'. Together they form a unique fingerprint.

Cite this