Which functions f : {0, 1} n → {0, 1} satisfy f (x ∧ y) = f (x) ∧ f (y) w.p. 1 -ε, where x, y are chosen uniformly at random? If ε = 0, it is not hard to check that f is either constant or an AND of a subset of the coordinates. Nehama [40] showed that when ε > 0, f must be O((nε) 1/3 )-close to a constant function or to an AND (in other words, Pr[f д] = O((nε) 1/3 ), where д is constant or an AND). The main result in this paper implies, as a corollary, a similar statement, in which the distance between f , д vanishes with ε, without any dependence on n.
Theorem 1.1. For each δ > 0 there is ε > 0 such that if a function f : {0, 1} n → {0, 1} satisfies
then f is δ -close to a constant or an AND.
Our technique is in fact more general, and allows us to study the multi-function version of this problem, in which we are interested in triples of functions f , д, h : {0, 1} n → {0, 1} that satisfy f (x ∧ y) = д(x) ∧ h(y) with probability at least 1 -ε. Quantitatively, we get a quasi-polynomial relationship between ε and δ , and more precisely ε = exp(-Θ(log 2 (1/δ ))), but we expect the correct dependency to be a polynomial.
Theorem 1.1 gives shows that the natural test above is a onesided error tester for the property of being an AND function. This question was first considered in [43], wherein the authors propose this test; being unable to analyze it the authors consider a more complicated tester and analyze it, but it comes at the cost of being less natural and having more queries as well as two sided error.
If we replace ∧ with ⊕ in the above problem, then the result corresponding to Theorem 1.1 is the well-known soundness of the Blum-Luby-Rubinfeld linearity test [7], that plays an important role in the construction of PCPs [1,2,24]. By now, many proofs for the soundness of this test are known: self-correction [7], Fourier analysis [6,24], induction [12]. Unfortunately, all of these proofs rely on ⊕ being a group operation (either directly or via Fourier analysis), and hence do not extend to our setting.
Our approach recasts the problem as determining the approximate eigenfunctions of a one-sided noise operator. Define the operator T acting on functions f : {0, 1} n → {0, 1} in the following way:
Using this operator, the premise of Theorem 1.1 implies that f is an approximate eigenfunction of this operator, i.e. Tf ≈ λ f , where λ = E[f ] is the average of f . Here, by approximate solution we mean that the L 1 distance between the two functions is small:
If we replace T with the usual two-sided noise operator T ρ , then a short spectral argument shows that if f is an approximate eigenfunction then it must be close to an exact eigenfunction of T ρ . Unfortunately, the spectral argument relies on orthogonality of eigenspaces of T ρ , a property which T doesn't satisfy (its eigenspaces are spanned by ANDs, which aren't orthogonal). Indeed, T has approximate eigenfunctions beyond ANDs, and below we give two examples f 1 and f 2 .
In f 2 , we stress that the function is defined probabilistically: for each x such that |x | < n/3 independently, we take f 2 (x) = 1 with probability λ < 1. It is easy to verify by case analysis that we have that Tf 1 ≈foot_0 2 f 1 , Tf 2 ≈ λ f 2 . Note however, that these functions are not counter-examples to the AND-test above, since both of them pass the test with some constant probability bounded away from 1.
Note that each one of the functions f 1 , f 2 is essentially composed of two, completely different "sub-functions": one defined on high Hamming-weight inputs, and another defined on low Hammingweight inputs. This suggests decoupling the two functions, and considering the generalized eigenvalue problem Tf = λд, where f : {0, 1} n → [0, 1] and д : {0, 1} n → {0, 1}.
Here f represents the low-weight part, and д represents the highweight part. We represent the probabilistic aspect of the low-weight part by allowing f to take on values in the interval [0, 1].
The two examples above corresponds to exact solutions of this generalized problem: T(x 1 ⊕ x 2 ) = 1 2 (x 1 ∨ x 2 ) and Tλ = λ • 1. Therefore, as a prerequisite to characterizing approximate eigenfunctions of T, we must first study exact solutions to the more general twofunction version. We show: Theorem 1.2. If f : {0, 1} n → [0, 1] and д : {0, 1} n → {0, 1} satisfy Tf = λд then either f = д = 0 or there exist disjoint subsets S 1 , . . . , S m ⊆ [n], where m log 2 (1/λ), such that
Moreover, if f is monotone then д is an AND and f = д.
Thus if Tf = λд then д is an "AND-OR" and f is the corresponding "AND-XOR" (or f = д = 0). When f is monotone, д must be an AND, and so f = д. Using Theorem 1.2, we can then actually solve the more general problem of characterizing approximate solutions to the equation Tf = λд. Theorem 1.3. If f : {0, 1} n → [0, 1] and д : {0, 1} n → {0, 1} satisfy Tf ≈ λд then either f ≈ д ≈ 0 or д is close to an AND-OR and f is close to an AND-XOR.
Moreover, if f is monotone then f , д are both close to a constant or to an AND.
We also show how to deduce Theorem 1.1 from Theorem 1.3. We remark that Theorem 1.3 is stated in a somewhat informal way: the closeness of the function f to an AND-XOR function has to be stated in a more subtle way (since otherwise it is false), and we defer this point to the formal statement of the theorems in Section 2.
Other noise rates. Nehama [40] also considers the more general equation
where each one of x 1 , . . . , x m is sampled uniformly and independently from {0, 1} n . We can reduce this problem, in a similar manner, to an eigenfunction of an appropriate operator T (m) , defined by
Our techniques also apply to such operators (and in fact to a slightly richer family of noise operators), and we prove variants of Theorem 1.2 and Theorem 1.3 in this case as well:
Furthermore, if T (m) f ≈ λд then either f ≈ д ≈ 0 or f , д are close to an AND.
One-sided error version. Finally, we consider the one-sided error version of the equation Tf = λд. That is, suppose we have a bounded function f : {0, 1} n → [0, 1], and a Boolean function д, such that with probability 1 -ε over x: (a) if д(x) = 1, then f (x ∧ y) λ with constant probability over y, and (b) if д(x) = 0 then f (x ∧ y) ε with probability 1 -ε over y.
We note that this condition is a relaxation of the approximate eigenvalue condition. In this case, we prove a weaker structural result than in Theorem 1.3, namely that д is close to a monotone junta.
Theorem 1.5. Suppose that the functions f : {0, 1} n → [0, 1] and д : {0, 1} n → {0, 1} satisfy the following condition: when д = 0, Tf is typically small; and when д = 1, Tf is typically at least λ. 1 Then д is close to a monotone Boolean junta. 2We remark that while the structural result in this case is weaker, it is for a good reason: for any monotone junta f , choosing д = f yields an approximate, one-sided error solution.
The seminal work of Kornhauser and Sager [32] discusses a situation where three cases A, B, C are considered in court, and by law, one should rule against C if and only if there is a ruling against both A and B. When several judges are involved, their opinions should be aggregated using a function f that preserves this law, that is, satisfies f (x ∧ y) = f (x) ∧ f (y); we say that f is an ANDhomomorphism. List and Pettit [34,35] showed that the only nonconstant aggregation functions that are AND-homomorphisms are the AND functions, known in the social choice literature as oligarchies.
Let the individual opinions of the judges be x 1 , . . . , x n on A, y 1 , . . . , y n on B, and x 1 ∧ y 1 , x 2 ∧ y 2 , . . . , x n ∧ y n on C. The characterization of robust judgement aggregation that we prove in this paper (Theorem 1.1) states that if typically f (x ∧ y) = f (x) ∧ f (y), then f is close to an oligarchy.
The characterization in terms of approximate eigenfunctions (Theorem 1.3) actually shows more. Suppose that opinions are aggregated according to a monotone function f which satisfies the following two conditions:
• There is rarely a ruling against C unless there is a ruling against A and a ruling against B. • Suppose that there is a ruling against A. If there is also a ruling against B, then with probability roughly q, there is a ruling against C.
(Formally, for typical
Then f must be close to an oligarchy or to a constant function, and q ≈ 1.
In fact, the second condition can be weakened significantly:
• Suppose that there is a ruling against A. Then with probability roughly λ, there is a ruling against C. Theorem 1.3 implies that f must be close to an oligarchy or to a constant function, and
Similarly, Theorem 1.5 shows that f has to be close to a monotone junta if the second condition above is replaced with either of the following two conditions:
• Suppose that there is a ruling against A. If there is also a ruling against B, then with probability at least q, there is a ruling against C. • Suppose that there is a ruling against A. Then with probability at least λ, there is a ruling against C. Thus our results do not only strengthen robust judgement aggregation in a quantitative way, but also in a qualitative way.
Our main result, Theorem 1.1, easily follows from Theorem 1.3, which is our main technical result. Below we sketch the proof idea of Theorem 1.3 (the proofs of Theorem 1.4 and Theorem 1.5 follow similar lines).
Suppose f , д are functions as in Theorem 1.3 that satisfy Tf ≈ λд. The first step of the proof is to show that the function д is close to a junta h, i.e. to a function depending only on constantly many variables. To get some intuition for that, note that if T was the standard noise operator, then the function Tf has exponentially decreasing tail and hence it is very concentrated on its low Fourier levels. When the operator T is the one-sided noise operator, one can actually use similar reasoning to claim that д again has an exponentially decaying tail (as observed by Lifshitz [33]). Since д is Boolean and д ≈ 1 λ Tf , this observation would then allow us to use structure theorems on Boolean functions (more specifically, a result of Bourgain [8] or of Kindler and Safra [31]) to conclude that д is (close to) a junta. Thus, ignoring some (important) technical details, one can think of д as a function of a constant number of variables, and since the proximity parameter between Tf and д can be taken to be very small (even in comparison to the number of variables д depends on), one may as well think of it as being 0. In other words, the problem essentially boils down to studying exact solutions to the equation Tf = д when n is constant, which is where Theorem 1.2 enters the picture. Using it, we prove the structural result on д; getting the structural result on f then amounts to averaging f over coordinates that д does not depend on (since those could be thought of as a "source of randomness" as in the example of f 2 (x) above), and then inverting the operator T acting on functions of a constant number of variables.
This ends the informal description of our techniques. We remark that actually composing the two components, namely the approximation by junta and the solution to the exact equation, is more subtle and requires some care. We also remark that in the case of one-sided error (Theorem 1.5), the Fourier-analytic argument alluded to above, which implies that д is close to a junta, does not seem to be applicable. We thus present an alternative, more combinatorial argument that captures this case as well.
1.4.1 Quantitative social choice theory. Social choice theory studies how to aggregate the opinion of a number of agents. Already in the 18th century, Condorcet [11] noted that natural aggregation rules often result in paradoxes. A large body of work has been developed in economics since the middle of the 20th century, in which it was shown that natural aggregation tasks have no good aggregation functions. The two most famous results in this area are Arrow's impossibility theorem [3,4] and the Gibbard-Satterthwaite (GS) manipulation theorem [21,45]. The questions of aggregation reemerged in the context of multi-agent systems in computer science, where the hope was that either the probability of paradoxical outcome is small, or there is computational difficulty in arriving at a paradoxical outcome, see e.g. [5] and the survey [18]. A sequence of results showed that this is not the case by proving strong and general quantitative versions of both Arrow's Theorem [28,29,37,38] and the GS Theorem [19,20,27,39], as well as results interpolating the two theorems [17].
The main motivation for the problem discussed in this paper is Judgement Aggregation. This problem is considered in a fascinating paper in the Yale Law Review by Kornhauser and Sager [32]. In particular, toward the end of the paper, the authors considered legal cases, where the judgement aggregation function f should satisfy f (x ∧ y) = f (x) ∧ f (y). They observe that this does not hold when f is the majority vote on three opinions. The failure of Majority, which mirrors the failure of Majority in ranking that was observed by Condorcet, led to work by List and Pettit [34,35], who characterized exactly the functions f that are AND-homomorphisms, i.e., oligarchies. The question of judgement aggregation has attracted much attention in philosophy, social epistemology, and artificial intelligence [44]. In the context of multiagent systems, when the number of agents is large, it makes sense to ask if it is possible to achieve approximate judgment aggregation. Our results show that this can only be achieved in the obvious way, i.e., by almost-oligarchies.
We note that the study of judgement aggregation extends well beyond AND-homomorphisms, to other types of homomorphisms, and indeed such a theory of polymorphisms is well-developed [13-16, 41, 46]. We leave if for future work to investigate robust versions of these results.
1.4.2 Property testing. The work of Blum, Luby and Rubinfeld [7] has been extended to more general settings by various authors. For example, Moore and Russell [36] and Gowers and Hatami [23] considered approximate representations of finite groups. Other authors had considered infinite groups, see for example the survey of Hyers and Rassias [26]. Theorem 1.1 generalizes Blum-Luby-Rubinfeld in a different direction, to approximate polymorphisms, where there is no group structure.
We remark that Theorem 1.1 implies that the soundness of a property testing algorithm of Parnas, Ron and Samorodnitsky [43], whose goal is to test whether the input function is a dictatorship or more generally an AND function. I.e., the tester should accept with high probability (preferably 1) if the function if an AND function, and reject with probability at least 2 3 if the function is ε-far from all AND functions. The authors proposed the following natural tester, which they were unable to analyze: test that f has expectation 1/2 and satisfies f (x ∧ y) = f (x) ∧ f (y). Instead, they proposed a somewhat less natural tester. Our results imply that their original tester also works.
We remark that can design a tester that only queries f on points distributed according to µ 1/2 at the cost of introducing an additional query. The tester samples x, y, z, w ∼ µ 1/2 conditioned on x∧y = z∧ w, and checks that f (x)∧ f (y) = f (z)∧ f (w). The soundness of this tester follows immediately from the soundness of the current tester by redefining for a ∼ µ 1/4 the value of f (a) to be the prominent value of f (x) ∧ f (y) where x, y ∼ µ 1/2 are sampled so that x ∧ y = a.
It is interesting to explore if there is a relationship between our results and different notions of approximate polymorphisms that appear in the literature [9,10], which were used to prove hardness of approximation results.
Organization. We formally state our results in Section 2. After some preliminaries in Section 3, we prove the various results in Sections 4, deferring the proof of the rest of the results to the full version of the paper. We close the paper by stating some open questions in Section 5.
Let µ p denote the p-biased measure on {0, 1} n . Let L 2 ({0, 1} n , µ p ) be the space of real-valued functions on {0, 1} n equipped with the inner product ⟨f , д⟩ = Ex∼µ p [f (x)д(x)]. Definition 2.1. For q p, the distribution (y, x) ∼ D(q, p) over {0, 1} n × {0, 1} n is the distribution in which for each i ∈ [n] independently, we have Pr [y i = 1] = q and Pr [x i = 1] = p, and always y i x i .
One way to generate inputs (y, x) ∼ D(q, p) that will be useful for us is as follows. Sample x ∼ µ p and z ∼ µ q/p independently, and output (x ∧ z, x). (Here ∧ refers to the coordinatewise AND operation, i.e. for each i ∈
For ρ ∈ (0, 1), define the one-sided operator T ↓ p,ρp as follows. For any function f : ({0, 1} n , µ ρp ) → {0, 1}, we define the function
Equivalently, we have
Next, we shall discuss the spectrum (eigenvectors and eigenvalues) of the operator T ↓ p,ρp . We remark that throughout this section, the parameters p and ρ should be thought of as constants bounded away from 0, 1.
For each S ⊆ [n], the function AND S : {0, 1} n → {0, 1} defined by AND S (x) = i ∈S x i is an eigenvector of T ↓ p,ρp with eigenvalue ρ |S | (we omit the easy proof). Moreover, these are the only eigenvectors of T ↓ p,ρp that are Boolean valued. 3 Our goal in this paper is to find a robust version of this characterization of the Boolean eigenvectors of T ↓ p,ρp . We say that a function f is an η-approximate eigenvector with eigenvalue λ, if
η (here and throughout the paper we will consider the ℓ 1 norm with respect to the µ p measure).
What can be said about the structure of Boolean, approximate eigenvectors of T ↓ p,ρp ? A natural conjecture would be that any such function has to be close to an exact eigenvector, which by Booleanity would have to be an AND-function over ≈ log ρ (λ) variables. However, this conjecture turns out to be false, as the following example demonstrates.
Set p = ρ = 1 2 , and consider the function f defined by f (x) = x 1 ∨ x 2 for inputs whose hamming weight is n/2 ± n log n, and by x 1 ⊕ x 2 for the rest of the inputs. It is easy to see that f is far from any AND function on the µ 1/2 measure, and we argue that
Except with probability o(1), the hamming weight of x, x ∧ z is roughly n/2, n/4 respectively, and we focus only on this event. We now consider two cases depending on the value f (x), and analyze each one of them separately. In case f (x) = 0, we get by definition that x 1 = x 2 = 0 so that (x ∧z) 1 = (x ∧z) 2 = 0 for any choice of z and in
so that for each fixed x such that (x 1 , x 2 ) (0, 0), this is a uniform unbiased bit, and in
Remark 2.2. It is worth noting that for any constant λ > 0, there are approximate eigenvectors of T ↓ 1/2,1/4 with eigenvalue λ (not only for λ = 2 -k ). Indeed, the function f that is constantly 1 on inputs with Hamming weight n/2 ± n log n, and on each other point x independently, we take f (x) = 1 with probability λ, is (with probability 1 -o( 1)) an approximate eigenvector with eigenvalue λ.
Since the previous example is essentially composed of two different functions (one around the middle slice and the other around the n/4slice), it makes sense to consider the two-function version of the approximate eigenvector problem. Namely, let f : ({0, 1} n , µ p ρ ) → {0, 1}, д : ({0, 1} n , µ p ) → {0, 1}, and λ ∈ (0, 1) be such that ∥T ↓ p,ρp f -д∥ 1 η. What can we say about f and д? We note that in this case, even the exact version of the problem, i.e. determining which functions can satisfy T ↓ p,ρp f = д, is already unclear (and in fact, as it turns out, understanding solutions to the exact problem is a key step in solving the approximate problem).
The version of the problem we will consider is actually more general and allows the function f to take values in [0, 1]. It turns out that the structure of the solutions heavily depends on ρ, and we consider three different regimes:
We remark that all of the results apply in particular for the original approximate eigenvector problem, i.e. the case f = д.
The first range, 0 < ρ < 1 2 , is the simplest, and we have the following result. η. Then either f , д are ε-close to the zero function, or there is a set T ⊆ [n] of size at most J such that:
(This range corresponds to the operators T (m) mentioned in Theorem 1.4.)
In the second range, ρ = 1/2, the structure of f and д may be more complicated (we have already seen an example in this range where д = OR T and f = XOR T for T of size 2).
Theorem 2.6. For any ζ > 0 there is m ∈ N such that for any ε > 0 there are η > 0, J ∈ N such that the following holds for all
Then there is a set T ⊆ [n] of size at most J , and a partition T = A 1 ∪ • • • ∪ A r for r m such that either f , д are ε-close to the zero function, or:
• д is ε-close to i ∈[r ] j ∈A i x j (i.e. to an AND-OR function of width at most m).
Both Theorem 2.3 and Theorem 2.6 can be shown to be qualitatively tight. For Theorem 2.6, for example, any pair of functions f , д where д is an AND-OR function and f is the corresponding AND-XOR function is an exact solution. To see that some averaging is needed to get a structure for f , note that given a pair of approximate solutions f , д, one may sub-sample f , i.e. change the value on each x such that f (x) = 1 with probability 1/2, to get a new approximate solution with λ/2, and f has no apparent structure (other than being a multiple of AND-XOR after averaging).
Quantitatively, the dependence of η on ε in Theorem 2.
The source of this difference is that in the case of Theorem 2.3 (and also in Theorem 2.7 and Theorem 2.8) we are able to prove stronger approximation by junta results than in Theorem 2.6. Namely, we show that there is J (ζ ) (independent of the proximity to junta parameter ε), such that if η is a sufficiently small function of ε, then д is ε-close to a J -junta. In the case of Theorem 2.6, we are forced to allow the size of the junta J to also depend on ε. As far as we know, in both cases the dependence of η on ε could be much better, perhaps even polynomial.
In the third range of parameters, 1 2 < ρ < 1, the solutions to the problem have a richer structure. It can be shown, for example, that there are ρ ∈ ( 1 2 , 1), λ ∈ (0, 1) and a function f : {0, 1} n → [0, 1] such that f and д(x) = Maj(x 1 , x 2 , x 3 ) are an exact solution to T ↓ 1/2,ρ/2 f = λд. In this case we only show a relatively weak structure, namely that д is close to a monotone junta (see Theorem 2.11). We remark that in order to get a stronger structure, one would only need to classify all exact solutions to the equation
We next present our result for a few special cases of interest, in which we are able to prove a stronger structure. The first result is concerned with the case when the approximate eigenvalue is large: Next, we consider the case in which f is a monotone function. In this case (and actually for a more relaxed case in which f is "almost monotone"), we show that д must be an AND function and f must be a multiple of that AND function after averaging. We also get quantitatively stronger relation between ε and η.
Theorem 2.8. For every ζ > 0, ε > 0 there exists η > 0 such that the following holds for all p, ρ ∈
• There exists T ⊆ [n] of size at most ⌈log(2/λ)⌉ and a function h that is either constant (in which case T = ∅) or AND T , such that ∥д -h∥ 1 ε.
The monotonicity condition in Theorem 2.8 can be relaxed to "almost monotonicity", in the sense that flipping any coordinate from 0 to 1 cannot decrease the value of the function too much. To define this relaxation more precisely we need the notion of negative influences:
The negative influence of a variable i on f , denoted by
where (x -i , x i = b) denoted the points y that agrees with x on all coordinates j i, and has value b on coordinate j.
(Note that whereas I i [f ] is the average of squared differences,
With this definition, Theorem 2.8 also holds when we relax the condition of monotonicity of f to the condition that all of its individual negative influences are small, i.e. I - i [f ] η for all i ∈ [n] (the proof of Theorem 2.8 in the full version achieves this stronger statement). One benefit of this relaxation is that it is able to capture the case of "judgement aggregation" as an immediate consequence.
1 -η, then one of the following cases must happen.
(1) f and at least one of the functions д or h are ε-close to the constant 0 function. (2) There is a set T ⊆ [n] such that f , д, h are all ε-close to AND T (each with respect to their input distribution).
Finally, we consider a more relaxed version of approximate solutions to T ↓ p,ρp f = д. We say functions f : {0, 1} n → [0, 1] and д : {0, 1} n → {0, 1} are one-sided error solutions with λ > 0 and error η if the following two conditions occur:
(1) T ↓ p,ρp f is very small on typical inputs x such that д(x) = 0:
η.
(2) T ↓ p,ρp f is bounded away from 0 on typical inputs x such that д(x) = 1:
Theorem 2.11. For any ε, ζ > 0 there are η > 0 and J ∈ N such that the following holds for any p, ρ ∈
and д : {0, 1} n → {0, 1} are one-sided error solutions with λ and error η, then д is ε-close to a monotone, Boolean J -junta.
We remark that any monotone junta д is a one-sided error approximate solution (by taking f = д), so Theorem 2.11 is tight with respect to the structure of д.
Organization. The proof of Theorem 2.6 is given in Section 4. The proofs of the rest of the results are deferred to the full version of the paper.
For any p ∈ (0, 1), we consider functions f : ({0, 1} n , µ p ) → R equipped with the inner product ⟨f , д⟩ = Ex∼µ p [f (x)д(x)]. We will use the Fourier-Walsh orthonormal basis χ
, where
is an orthonormal basis, we have Parseval's
f p (S) 2 . We will need a few more notions and results from Fourier analysis, such as the Junta Theorems of [8,31] and the Sensitivity Conjecture proved recently by [25], which we present below.
For a function f : ({0, 1} n , µ p ) → R and a coordinate i ∈ [n], we define the p-biased influence of variable i to be
When the bias parameter is clear from context, we often write
We will also use the notion of negative influences as given in Definition 2.9. We have the following simple fact, stating that averaging may only decrease negative influences. The proof is deferred to the full version of the paper.
We also need the following fact that relates negative influences and distance from monotonicity. Fact 3.2. For all p ∈ (0, 1), n ∈ N and τ > 0, if the function
We remark that the above fact is inspired by [22], wherein a similar statement was proved for Boolean functions for p = 1/2, with a better bound (nτ ). The proof is deferred to the full version of the paper.
We will use Bourgain's Theorem [8]; the sharp version below is proved in [30]. For k ∈ N, the Fourier tail W k [f ] is defined to be
, then f is ε-close to a J -junta h.
Furthermore, h only depends on variables i such that I i [д] τ .
We also need the following result of Kindler and Safra. While being quantitatively weaker in some regards, it has an important feature that will be important for us and is missing from Theorem 3.3. The size of the junta in the result of Kindler and Safra only depends on the parameter k, as opposed to also on the closeness parameter ε as in Theorem 3.3.
δ , then f is ε-close to a junta of size J (m, ζ ).
For any f : {0, 1} n → {0, 1} and x ∈ {0, 1} n , the sensitivity of f at x is equal to the number of coordinates i ∈
The degree of a function deg(f ) is the maximal size of S such that f p (S) 0 (we remark that this is easily seen to be independent of p).
We will use the following recent result of Huang [25] (formerly known as the sensitivity conjecture [42]) in our proof. We remark that quantitatively weaker results that were known earlier (such as the bound s(f ) Ω(log(deg(f )))) would have been enough for us, but yield to a loss in several parameters.
). For any f : {0, 1} n → {0, 1} we have that s(f ) deg(f ).
In this section, we prove Theorem 2.6. Since we will always consider the downwards noise operator T ↓ p,p/2 , we denote it succinctly by T.
Lemma 4.1. For any ζ > 0 and n ∈ N there exists η 0 > 0 such that the following holds for all p
• д is an AND-OR function of width r , where r ⌈log(2/ζ )⌉. • Let ϕ be the corresponding AND-XOR function.
This section is devoted to the proof of this lemma, and the proof is divided into several claims. It will be convenient for us to identify vectors in {0, 1} n with subsets of [n] by identifying a vector with its support, and consequently think of the inputs of functions as subsets of [n]. The definition of the operator T to these language is immediate: Since д is monotone, one can discuss its minterms, i.e. sets M ⊆ [n] such that д(M) = 1 but for all A M, д(A) = 0. The following lemma asserts that the value of f on any minterm of д is determined (up to a small error). We next wish to argue all minterms of д are of the same size, and towards this end (and also in other places in the argument) the following proposition will be useful.
Note that for any Y ⊆ Z ,
in which case the sum is 1, and so we get that
Therefore the triangle inequality implies that
To complete the proof, we observe that by the binomial formula
We now show two consequences of the above proposition. First, we show that all minterms of д have the same size.
where the last inequality is by the choice of η. This implies that |M ′ | |M |. The second inequality is proved analogously.
Denote the size of a minterm of д by m, and note that m ⌈log(2/λ)⌉. Indeed, letting M be any minterm of д, by Claim 4.3 we get that λ2 m f (M) + 4 m η 2.
We next show that the value of f in a point B must be either close to 0 or close to 2 m λ. For each A M, by the induction hypothesis f (A ∪ Z ) is either close to 0 (i.e. at most 4 |A∪Z | 2 η) or close to 2 m λ (more precisely, up to ±4 |A∪Z | η).
• If there is A ⋆ M that falls into the second case, then by non-negativity of f we get that f (B) is equal to
where in the last inequality we used A ⋆ m -1, and the claim is proved for B. • Otherwise, by the triangle inequality
We are now able to restate Proposition 4.4 in a more convenient form. For each pair of disjoint sets Then there is a unique A ⋆ ⊆ B such that:
Proof. For the first item, if for all A ⊆ B it holds that f (A∪Z ) 4 n 2 η, then by Proposition 4.4 we have 2 m λ A⊆B f (A ∪ Z )+6 n η 4 n 2 +3n η, which contradicts the choice of η. Therefore, by Claim 4.6 there is
For the second item, assume towards contradiction there are two such A 1 , A 2 . By Proposition 4.4 we have
and therefore 2 m λ 6 n+1 η, which is a contradiction to the choice of η.
For the third item, note that
and since д is Boolean-valued it follows that д(A ⋆ ∪ Z ) = 1. Also, for any A A ⋆ we have
where in the second inequality we used the definition of T and the second item. Since д is Boolean we get that д(A ∪ Z ) = 0.
To simplify notation, for the rest of the section we often say "the value of f (S) is close to 2 m λ" to express that | f (S) -2 m λ| 4 n η and "the value of f (S) is close to 0" to express that f (S) 4 n 2 η.
Consider the m-uniform hypergraph H = ([n], E) whose edges are the minterms of д. In the remainder of this section we show that H is a complete m-partite hypergraph, which is easily seen to be equivalent to д being an ANR-OR function of width m. Towards this end, we will define a coloring χ : •
We first show that each minterm of д is colored using only elements from [m] (as opposed to ⊥). Proof. Assume towards contradiction that this is not the case, and let v ∈ M be such that χ (v) = ⊥. Then by definition of χ this means that f (B ∪ {v}) is close to 2 m λ, and since B is a minterm of д we also know, by Claim 4.3, that f (B) is close to 2 m λ. This gives us two points in X (M, B \ M) whose f -value is close to 2 m λ, in contradiction to Corollary 4.7.
Next, we show that each minterm of д is rainbow colored by χ . Claim 4.9. Let M ∈ E be a minterm of д. Then M is rainbow colored.
Proof. Write M = {v 1 , . . . , v m }, and assume towards contradiction the statement is false. Then there are v i , v j that are assigned the same color by χ , and without loss of generality we may assume χ
However, note that these are two distinct points in X (M, B \M), and thus we get a contradiction to the second item in Corollary 4.7.
Note that the definition of the coloring χ may depend on the minterm B chosen initially to define it. The following claim shows that this is actually not the case -and more precisely that if we use a different minterm B ′ to define a coloring χ ′ , then there is a permutation π on [m] such that χ ′ = π • χ . Proof. Since B is a minterm of д, it follows by Claim 4.9 that it is rainbow colored by both χ and χ ′ , so we define π ∈ S m by π (χ ′ (b i )) = χ (b i ). We define χ = π • χ ′ and show that χ = χ . Let v B, and assume without loss of generality χ (v) = m. Then by definition of χ we must have that {b 1 , . . . , b m-1 , v} is a minterm of д, and hence by Claim 4.9 it must be rainbow colored by χ . Since χ agrees with χ on b 1 , . . . , b m-1 , we must have χ (v) = m, and we are done.
Lastly, we show that each rainbow colored set of size m is a minterm of д.
Let χ ′ be the coloring defined by B ′ . By Claim 4.9 we get that χ ′ = π • χ for some π ∈ S m , and in particular as M is rainbow colored by χ it is also rainbow colored by χ ′ . Since |B ′ ∩ M | = k + 1 we may apply the induction hypotehsis on B ′ with the coloring χ ′ to conclude that M is a minterm of д, as required.
It follows that the function д is the function i ∈[m] j ∈A i x j where A i = χ -1 (i). To complete the proof of Lemma 4.1 we must establish the structural result for f , which we do by inverting f .
where in the last equality we used the fact that adding the summand corresponding to A = B, the sum would be 0. Plugging that into the previous equality and rearranging finishes the inductive step. Let ϕ = m i=1 j ∈A i x j . We show that Tϕ = 2 -m д. Since T is invertible by Claim 4.12 and Tψ = λд, we get ψ = 2 m λϕ, and hence Claim 4.13 implies that f is 3 n η-close to 2 m λϕ in L ∞ , as required.
Claim 4.14. Let A 1 , . . . , A m be disjoint, non-empty sets, and let ϕ = m i=1 j ∈A i x j , д = m i=1 j ∈A i x j . Then Tϕ = 2 -m д.
Proof. Fix B ⊆ [n], and let B i = B ∩ A i for each i.
If д(B) = 0, then B i = ∅ for some i, without loss of generality i = 1. Thus, for any C ⊆ B we have that C ∩ A 1 = ∅, and hence ϕ(C) = 0, so Tϕ(B) = 0.
If д(B) = 1, then B i ∅ for all i. Let C ⊆ B be chosen uniformly at random, and denote C i = C ∩ A i . Note that the distribution of C 1 , . . . , C m is of independent uniform subsets of B 1 , . . . , B m , and as such the parity of the size of each C i is a uniform and independent bit. Thus,
This completes the proof of Lemma 4.1.
In this section we use Lemma 4.1 to deduce Theorem 2.6, and we first sketch the argument. Given an approximate solution f , д, we first observe that the function д is noise insensitive -that is, has a small Fourier tail -and hence deduce from Theorem 3.3 that it is close to a junta. We then show that for almost all restrictions β outside the junta variables, we can associate a bounded function fβ such that fβ , д β are a solution to the equation in L ∞ , and we may deduce some structure for д β and fβ . Using the fact that the restricted variables barely affect the function д (since it is junta) one can thus deduce the necessary AND-OR structure from д. To get the structural result for the function f , slightly more work is needed. We show that eliminating ORs that are too wide from the д β 's, almost all of them become the same function, and we show that after averaging over the removed variables, f is close to a multiple of the corresponding AND-XOR function.
We first give several statements that will be useful for us in the proof. The following lemma from [33] shows the effect of the operator T ↓ p,p ρ on the Fourier expansion of a function. Using the previous lemma we may show that if f , д are approximate solutions, then д has an exponentially small tail.
Proof. Since f , д are bounded between 0 and 1, Tf -λд is bounded between -1, 1 at each point and therefore we get that ∥Tf -λд∥ 2 2 ∥Tf -λд∥ 1 η. Using Parseval's inequality (and Lemma 4.15 to get the Fourier coefficients of Tf on µ p ), we get that,
where in the last inequality we used Parseval to bound the sum of Fourier coefficients of f by 1 and ρ 2 ρ.
Second, the following will be useful for us in the pruning process of the wide ORs. Lemma 4.17. Suppose that д 1 , д 2 are AND-OR functions of width at most d that are ε-close with respect to µ p , and let γ = 2p -d ε. Let ψ 1 ,ψ 2 be the truncations of д 1 , д 2 respectively resulting by removing all ORs containing more than log 1/(1-p) (1/γ ) variables.
Then ψ 1 = ψ 2 , and furthermore this function is dγ -close to д 1 .
Proof. We say an OR of д 1 is small if the number of variables in it is at most log 1/(1-p) (1/γ ), and let A 1 be a small OR of д 1 . We claim that there is a small OR of д 2 , which will be denoted by A 2 , that contains A 1 . Assume towards contradiction that this is not the case. Thus, restricting A 1 -variables to 0, the restricted function (д 2 ) A 1 →0 does not become identically 0 and it is still an AND-OR function of width at most d, and therefore it gets the value 1 with probability at least p d . Since the probability that all of the variables in A 1 get the value 0 is at least (1 -p) log 1/(1-p) (1/γ ) = γ , we get that Pr
However, note that on any such x we have д 1 (x) = 0 and д 2 (x) = 1, and by assumption the probability mass on such x's is at most ε, so we get that ε γp d and contradiction. Therefore, for each small OR of д 1 there is a small OR in д 2 containing it and vice versa. As the ORs in each function are disjoint in variables, it follows that each small OR of д 1 appears in д 2 and vice versa, so in other words ψ 1 = ψ 2 .
Finally, since д 1 and ψ 1 may differ only when there is an OR of size at least log 1/(1-p) (1/γ ) in д 1 that evaluates to 0, and there are at most d such clauses, it follows from the union bound that Pr x [д 1 (x) ψ 1 (x)] dγ .
We are now ready to prove Theorem 2.6.
Proof of Theorem 2.6. Fix ζ , ε > 0 from Theorem 2.6 (we assume ε > 0 is small enough) and choose m = ⌈log(2/ζ )⌉. Let C = C(ζ ) be from Theorem 3.3, choose η 1 = ζ 2 ε 2 /(4C log(1/ε)), and pick τ , J from Theorem 3.3 for ε and k = ⌈log(1/η 1 )⌉. Later in the proof we will also define η 2 and subsequently take η = min(η 1 , η 2 ).
Let f , д be functions as in the statement of Theorem 2.6, and set k = ⌈log(1/η 1 )⌉. From Lemma 4.16 we have that W
ε/(Ck), and Theorem 3.3 implies that there is T ⊆ [n] of size J such that д is ε 2 -close to a T -junta. Take η 4.1 from Lemma 4.1 for ζ and n = J , and set η 2 = 6 -J η 4.1 ε 2 . We write points x ∈ {0, 1} n as (α, β) where α ∈ {0, 1} T and β ∈ {0, 1} [n]\T . For each β ∈ {0, 1} [n]\T , define fβ : {0, 1} T → [0, 1] and д β : {0, 1} T → {0, 1} by
Therefore Markov's inequality implies that with probability at least 1 -ε over β ∼ µ p we have ∥T fβλд β ∥ 1 6 -J εη 4.1 , in which case β ∈ B. In particular, we conclude that 1 -4ε. We may already argue that д is close to the AND-OR function д β ⋆ , however that will not be strong enough to establish the structural result for f and hence we prove a stronger statement. Namely, we show that if we truncate д β by removing the wide ORs, then almost all of them will produce the same AND-OR function ψ .
Proving the structural result for д. For each β ∈ B ′ , let ψ β be the AND-OR function д β where we remove from it all ORs whose width exceeds log 1/(1-p) (1/(2p -m ε)). From Lemma 4.17 we get that there is an AND-OR function ψ (namely, ψ β ⋆ ) such that ψ β = ψ and ∥д β -ψ ∥ i.e. д is close to the AND-OR function ψ . Let T ′ ⊆ T be the set of variables that appear in ψ , and write α ∈ {0, 1} T as α = (α 1 , α 2 ), where α 1 ∈ {0, 1} T ′ and α 2 ∈ {0, 1} T \T ′ .
Proving the structural result for f . We show that averaging outside T ′ makes f close to a multiple of ϕ, where ϕ is the AND-XOR function corresponding to ψ . For each β ∈ B ′ we denote by ϕ β the AND-XOR function corresponding to д β . Since A(α 1 ) = E α 2 ,β ′ ∼µ p ρ [f (α 1 , α 2 , β ′ )], this shows that after averaging outside T ′ , the function f is O ζ (ε)-close to Kϕ, and we next show that one may replace K by λ2 r , where r is the width of ϕ, and retain this closeness.
If ψ = 0 then ϕ = 0 so the value of K does not matter, so we assume henceforth that ψ 0, in which case we clearly have ∥ψ ∥ 1 p m . Since T is a contraction, ∥TA-K • Tϕ ∥ 1 ∥A-Kϕ ∥
Our work raises many open questions. Perhaps the most obvious is the quantitative aspect of our results:
Open Question 1. What is the optimal dependence between ε and δ in Theorem 1.1?
We can ask a similar question about the various results listed in Section 2.
Nehama [40] showed that if we allow ε to depend on n, then we can choose ε = Θ(δ 3 /n). Theorem 1.1 eliminates the dependence on n in return for an exponential dependence on δ . We conjecture that Theorem 1.5 holds for ε = δ Θ (1) .
Nehama situates Theorem 1.1 in the larger context of approximate judgement aggregation, or equivalently, approximate polymorphisms. He considers not only functions satisfying
but also functions satisfying
showing (using linearity testing) that the latter must be close to XORs. More generally, we can replace ∧, ⊕ with an arbitrary Boolean function (or even a function on a larger domain):
Open Question 2. Fix ϕ : {0, 1} m → {0, 1}. Suppose f : {0, 1} n → {0, 1} satisfies f (ϕ(x 1 , . . . , x m )) ≈ ϕ(f (x 1 ), . . . , f (x m )) for random x 1 , . . . , x m ∈ {0, 1} n , where ϕ(x 1 , . . . , x m ) signifies elementwise application. What can we say about f ? Dokow and Holzman [13] showed (essentially) that when ϕ is a non-trivial function which is not an AND or an XOR, then the only exact solutions are dictatorships. We conjecture that when ϕ is such that the only exact solutions are dictatorships, then approximate solutions are approximate dictatorships.
Finally, let us mention the following tantalizing question:
Open Question 3. What can be said about functions f : {0, 1} n → {0, 1} satisfying
+ ε?
We remark that the 3 4 bound on the right hand side is natural in light of semi-random functions f : {0, 1} n → {0, 1}, chosen by taking f (x) to be a uniform bit when |x | ≈ 1 2 n, and f (x) = 0 otherwise.
In contrast, in Theorem 1.3 we ask that Tf be typically close to λ.
A junta is a function depending on a constant number of coordinates.
To see that, note that any function f can be written as a linear combination of AND functions, and if f is an eigenvector then all of these ANDs are of the same size, say with coefficients α 1 , . . . , α m . Considering the value of f on the minterms of these ANDs, one concludes that all of the α 's must be 1, and considering the value of f on the all-1 string, one concludes that m = 1.
Alternatively, note that A M f (A) |B |=m-1 A⊆B f (A), and take B maximizing A⊆B f (A).