Analysis of Boolean functions
In mathematics and theoretical computer science, analysis of Boolean functions is the study of real-valued functions on formula_1 or formula_2 (such functions are sometimes known as pseudo-Boolean functions) from a spectral perspective. The functions studied are often, but not always, Boolean-valued, making them Boolean functions. The area has found many applications in combinatorics, social choice theory, random graphs, and theoretical computer science, especially in hardness of approximation, property testing, and PAC learning. Basic concepts. We will mostly consider functions defined on the domain formula_2. Sometimes it is more convenient to work with the  domain formula_1 instead. If formula_5 is defined on formula_2, then the corresponding function defined on formula_1 is Similarly, for us a Boolean function is a formula_9-valued function, though often it is more convenient to consider formula_10-valued functions instead. Fourier expansion. Every real-valued function formula_11 has a unique expansion as a multilinear polynomial: This is the Hadamard transform of the function formula_5, which is the Fourier transform in the group formula_14. The coefficients formula_15 are known as "Fourier coefficients", and the entire sum is known as the "Fourier expansion" of formula_5. The functions formula_17 are known as "Fourier  characters", and they form an orthonormal basis for the space of all functions over formula_2, with respect to the inner product formula_19. The Fourier coefficients can be calculated using an inner product: In particular, this shows that formula_21, where the expected value is taken with respect to the uniform distribution over formula_2. Parseval's identity states that If we skip formula_24, then we get the variance of formula_5: Fourier degree and Fourier levels. The "degree" of a function formula_11 is the maximum formula_28 such that formula_29 for some set formula_30 of size formula_28. In other words, the degree of formula_5  is its degree as a multilinear polynomial. It is convenient to decompose the Fourier expansion into "levels": the Fourier coefficient formula_15 is on level formula_34. The "degree formula_28" part of formula_5 is Using this we can define the noise stability and the noise sensitivity, as before. Russo–Margulis formula. The Russo–Margulis formula (also called the Margulis–Russo formula) states that for monotone Boolean functions formula_38, Both the influence and the probabilities are taken with respect to formula_40, and on the right-hand side we have the average sensitivity of formula_5. If we think of formula_5 as a property, then  the formula states that as formula_43 varies, the derivative of the probability that formula_5 occurs at formula_43 equals the average sensitivity at formula_43. The Russo–Margulis formula is key for proving sharp threshold theorems such as Friedgut's. Gaussian space. One of the deepest results in the area, the invariance principle, connects the distribution of functions on the Boolean cube formula_2 to their distribution on "Gaussian space", which is the space formula_48 endowed with the standard formula_49-dimensional Gaussian measure. Many of the basic concepts of Fourier analysis on the Boolean cube have counterparts in Gaussian space: Gaussian space is  more symmetric than the Boolean cube (for example, it is rotation invariant), and supports continuous arguments which may be harder to get through in the discrete setting of the Boolean cube. The invariance principle links the two settings, and allows deducing results on the Boolean cube from results on Gaussian space. Basic results. Friedgut–Kalai–Naor theorem. If formula_55 has degree at most 1, then formula_5 is either constant, equal to a coordinate, or equal to the negation of a coordinate. In particular, formula_5 is a "dictatorship": a function depending on at most one coordinate. The Friedgut–Kalai–Naor theorem , also known as the "FKN theorem", states that if formula_5 "almost" has degree 1 then it is "close" to a dictatorship. Quantitatively, if formula_55 and formula_60, then formula_5 is formula_62-close to a dictatorship, that is, formula_63 for some Boolean dictatorship formula_64, or equivalently, formula_65 for some Boolean dictatorship formula_64. Similarly, a Boolean function of degree at most formula_28 depends on at most formula_68 coordinates, making it a "junta" (a function depending on a constant number of coordinates), where formula_69 is an absolute constant equal to at least 1.5, and at most 4.41, as shown by Wellens. The Kindler–Safra  theorem generalizes the Friedgut–Kalai–Naor theorem to this setting. It states that if formula_55 satisfies formula_71 then formula_5 is formula_62-close to a Boolean function of degree at most formula_28. Kahn–Kalai–Linial theorem. The Poincaré inequality for the Boolean cube (which follows from formulas appearing above) states that for a function formula_11, This implies that formula_77. The Kahn–Kalai–Linial theorem, also known as the "KKL theorem", states that if formula_5 is Boolean then formula_79. The bound given by the Kahn–Kalai–Linial theorem is tight, and is achieved by the "Tribes" function of Ben-Or and Linial : The Kahn–Kalai–Linial theorem was one of the first results in the area, and was the one introducing hypercontractivity into the context of Boolean functions. Friedgut's junta theorem. If formula_55 is an formula_82-junta (a function depending on at most formula_82 coordinates) then formula_84 according to the Poincaré inequality. Friedgut's theorem is a converse to this result. It states that for any formula_85, the function formula_5 is formula_87-close to a Boolean junta depending on formula_88 coordinates. Combined with the Russo–Margulis lemma, Friedgut's junta theorem implies that for every formula_43, every monotone function is close  to a junta with respect to formula_90 for some formula_91. Invariance principle. The invariance principle generalizes the Berry–Esseen theorem to non-linear functions. The Berry–Esseen theorem states (among else) that if formula_92 and no formula_93 is too large compared to the rest, then the distribution of formula_5 over formula_2 is close to a normal distribution with the same mean and variance. The invariance principle (in a special case) informally states that if formula_5 is a multilinear polynomial of bounded degree over formula_97 and all influences of formula_5 are small, then the distribution of formula_5 under the uniform measure  over formula_2 is close to its distribution in Gaussian space. More formally, let formula_101 be a univariate Lipschitz function, let formula_102, let formula_103, and let formula_104. Suppose that formula_105. Then By choosing appropriate formula_101, this implies that the distributions of formula_5 under both measures are close in CDF distance, which is given by formula_109. The invariance principle was the key ingredient in the original proof of the "Majority is Stablest" theorem. Some applications. Linearity testing. A Boolean function formula_55 is "linear" if it satisfies formula_111, where formula_112. It is not hard to show that the Boolean linear functions are exactly  the characters formula_17. In property testing we want to test whether a given function is linear. It is natural to try the following test: choose formula_114 uniformly at random, and check that formula_111. If formula_5 is linear then it always passes the test. Blum, Luby and Rubinfeld showed that if the test passes with probability formula_117 then formula_5 is formula_62-close to a Fourier character. Their proof was combinatorial. Bellare et al. gave an extremely simple Fourier-analytic proof, that also shows that if the test succeeds with probability formula_120, then formula_5 is correlated with a Fourier character. Their proof  relies on the following formula for the success probability of the test: Arrow's theorem. Arrow's impossibility theorem states that for three and more candidates, the only unanimous voting rule for which there is always a Condorcet winner is a dictatorship. The usual proof of Arrow's theorem is combinatorial. Kalai gave an alternative proof of this result in the case of three candidates using Fourier analysis. If formula_55 is the rule that assigns a winner among two candidates given their relative orders in the votes, then the probability that there is a Condorcet winner given a uniformly random  vote is formula_124, from which the theorem easily follows. The FKN theorem implies that if formula_5 is a rule for which there is almost always a Condorcet winner, then formula_5 is close to a dictatorship. Sharp thresholds. A classical result in the theory of random graphs states that the probability that a formula_127 random graph is connected tends to formula_128 if formula_129. This is an example of a "sharp threshold": the width of the "threshold window", which is formula_130, is asymptotically smaller than the threshold itself, which is roughly formula_131. In contrast, the probability that a formula_127 graph contains a  triangle tends to formula_133 when formula_134. Here both the threshold window and the threshold itself are formula_135, and so this is a "coarse threshold". Friedgut's sharp threshold theorem states, roughly speaking, that a monotone graph property (a graph property is a property which doesn't depend on the names of the vertices) has a sharp threshold unless it is correlated with the appearance of small subgraphs. This theorem has been widely applied to analyze random graphs and percolation. On a related note, the KKL theorem implies that the width of threshold window is always at most formula_136. Majority is  stablest. Let formula_137 denote the majority function on formula_49 coordinates. Sheppard's formula gives the asymptotic noise stability of majority: This is related to the probability that if we choose formula_140 uniformly at random and form formula_141 by flipping each bit of formula_142 with probability formula_143, then the majority stays the same: There are Boolean functions with larger noise stability. For example, a dictatorship formula_145 has noise stability formula_54. The Majority is Stablest theorem states, informally, then the only functions having noise stability larger than majority have influential coordinates. Formally, for every formula_85 there exists formula_148 such that if formula_55  has expectation zero and formula_150, then formula_151. The first proof of this theorem used the invariance principle in conjunction with an isoperimetric theorem of Borell in Gaussian space; since then more direct proofs were devised. Majority is Stablest implies that the Goemans–Williamson approximation algorithm for MAX-CUT is optimal, assuming the unique games conjecture. This implication, due to Khot et al., was the impetus behind proving the theorem.