Revisiting Bourgain-Kalai and Fourier Entropies
Authors:
- Muli SafraMSMuli Safra
Preprint
Abstract
The total influence of a function is a central notion in analysis of Boolean functions, and characterizing functions that have small total influence is one of the most fundamental questions associated with it. The KKL theorem and the Friedgut junta theorem give a strong characterization of such functions whenever the bound on the total influence is $o(\log n)$, however, both results become useless when the total influence of the function is $\omega(\log n)$. The only case in which this logarithmic barrier has been broken for an interesting class of function was proved by Bourgain and Kalai, who focused on functions that are symmetric under large enough subgroups of $S_n$. In this paper, we revisit the key ideas of the Bourgain-Kalai paper. We prove a new general inequality that upper bounds the correlation between a Boolean function $f$ and a real-valued, low degree function $g$ in terms of their norms, Fourier coefficients and total influences. Some corollaries of this inequality are: 1. The Bourgain-Kalai result. 2. A slightly weaker version of the Fourier-Entropy Conjecture. More precisely, we prove that the Fourier entropy of the low-degree part of $f$ is at most $O(I[f]\log^2 I[f])$, where $I[f]$ is the total influence of $f$. In particular, we conclude that the Fourier spectrum of a Boolean function is concentrated on at most $2^{O(I[f]\log^2 I[f])}$ Fourier coefficients. 3. Using well-known learning algorithms of sparse functions, the previous point implies that the class of functions with sub-logarithmic total influence (i.e. at most $O(\log n/(\log \log n)^2)$) is learnable in polynomial time, using membership queries.
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- A Composition Theorem for the Fourier Entropy-Influence ConjectureLecture Notes in Computer Science, 2013
- The Fourier Entropy–Influence Conjecture for Certain Classes of Boolean Functions2011
- Intersecting Families are Essentially Contained in JuntasCombinatorics, Probability and Computing, 2009
- On the distribution of the fourier spectrum of Boolean functionsIsrael Journal of Mathematics, 2002
- Boolean Functions With Low Average Sensitivity Depend On Few CoordinatesCombinatorica, 1998
- An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform DistributionJournal of Computer and System Sciences, 1997
- Influences of Variables and Threshold Intervals under Group SymmetriesGeometric and Functional Analysis, 1997
- Every monotone graph property has a sharp thresholdProceedings of the American Mathematical Society, 1996
- An O(nlog log n) Learning Algorithm for DNF under the Uniform DistributionJournal of Computer and System Sciences, 1995
- The influence of variables on Boolean functions1988