4069:
2434:
3855:
8062:
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
11788:
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
2124:
6333:
3363:
4389:
7234:
3189:
10440:
7486:
4976:
4064:{\displaystyle y_{i}={\begin{cases}x_{i}&{\text{w.p. }}\rho ,\\z_{i}&{\text{w.p. }}1-\rho .\end{cases}}\quad {\text{or}}\quad y_{i}={\begin{cases}x_{i}&{\text{w.p. }}{\frac {1+\rho }{2}},\\-x_{i}&{\text{w.p. }}{\frac {1-\rho }{2}}.\end{cases}}}
3553:
9294:
7039:
5714:
4570:
6799:
2863:
759:
8960:
6658:
12599:
12025:
9147:
9039:
2429:{\displaystyle {\begin{aligned}&\operatorname {Inf} _{i}=\operatorname {E} \left=\sum _{S\ni i}{\hat {f}}(S)^{2},\\&f^{\oplus i}(x_{1},\ldots ,x_{n})=f(x_{1},\ldots ,x_{i-1},-x_{i},x_{i+1},\ldots ,x_{n}).\end{aligned}}}
11212:
473:
6139:
1499:
1079:
5189:
11372:
6079:
1365:
11925:
10180:
7935:
5502:
3200:
10247:
4205:
6466:
4793:
12526:
10071:
2129:
1908:
1151:
7050:
2998:
2032:
1210:
9573:
3029:
5400:
5079:
12296:
10255:
8874:
7316:
5315:
4801:
4727:
4177:
2116:
1567:
607:
10817:
8007:
8741:
8339:
12471:
11299:
10673:
9374:
8692:
8625:
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
8290:
8143:
7308:
2610:
3440:
11553:
9728:
8442:
9452:
3435:
2658:
11301:
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
3753:
2496:
9162:
6943:
4476:
12179:
11742:
830:
12844:
11629:
10905:
9886:
8512:
7797:
The counterpart of total influence or average sensitivity for the indicator function of a set is
Gaussian surface area, which is the Minkowski content of the boundary of the set.
4424:
3827:
3649:
1631:
10581:
6908:
6669:
5229:
4114:
3595:
2733:
12376:
12124:
12076:
9481:
5597:
5589:
615:
11096:
7730:
6866:
11059:
8790:
8388:
11010:
10964:
10736:
1736:
868:
12352:
The
Majority is Stablest theorem states, informally, then the only functions having noise stability larger than majority have influential coordinates. Formally, for every
11779:
11709:
9968:
9817:
9521:
7697:
5811:
1394:
1260:
969:
293:
192:
110:
11841:
11506:
5925:
5893:
332:
231:
68:
12402:
9649:
8882:
8592:
5005:
10844:
6935:
6509:
5036:
4671:
923:
10103:
9623:
7516:
5956:
511:
4633:
4468:
543:
12531:
11664:
11594:
11466:
5754:
5530:
12347:
12327:
11953:
10463:
9991:
9755:
8623:
8053:
7788:
6827:
5257:
4197:
3773:
3670:
3021:
8033:
6128:
3698:
1766:
5834:
12144:
11945:
11419:
11399:
11116:
11030:
10984:
10483:
9926:
9906:
9840:
9775:
9596:
9501:
9414:
9394:
9066:
8810:
8761:
8555:
8532:
8462:
8359:
8214:
8183:
8163:
7750:
7636:
7616:
7596:
7576:
7556:
7536:
6501:
6380:
6360:
6102:
5854:
5119:
5099:
4613:
4593:
4448:
3847:
2934:
2914:
2894:
2725:
2698:
2678:
2516:
2457:
2060:
1951:
1931:
1812:
1791:
1691:
1671:
1651:
1587:
1414:
896:
789:
251:
11232:
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
9071:
9299:
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.
8968:
6328:{\displaystyle \omega _{S}(x)=\left({\sqrt {\frac {p}{1-p}}}\right)^{|\{i\in S:x_{i}=0\}|}\left(-{\sqrt {\frac {1-p}{p}}}\right)^{|\{i\in S:x_{i}=1\}|}.}
11124:
340:
12880:
1422:
13187:
5121:
at the final state. This Markov chain is generated by the
Laplacian of the Hamming graph, and this relates total influence to the noise operator.
974:
5127:
11304:
5964:
1268:
11854:
7763:
The counterpart of the
Fourier expansion in Gaussian space is the Hermite expansion, which is an expansion to an infinite sum (converging in
10108:
3358:{\displaystyle \operatorname {I} ^{(\rho )}={\frac {d}{d\rho }}\operatorname {Stab} _{\rho }=\sum _{S}|S|\rho ^{|S|-1}{\hat {f}}(S)^{2}.}
4384:{\displaystyle \operatorname {Stab} _{\rho }=\operatorname {E} _{x;y\sim N_{\rho }(x)}=\sum _{S\subseteq }\rho ^{|S|}{\hat {f}}(S)^{2}.}
7811:
5408:
10185:
6392:
4732:
7229:{\displaystyle (T_{\rho }f)(x)=\sum _{S\subseteq }\rho ^{|S|}{\hat {f}}(S)\omega _{S}(x)=\operatorname {E} _{y\sim N_{\rho }(x)}.}
6133:
The classical
Fourier characters are no longer orthogonal with respect to this measure. Instead, we use the following characters:
12895:
12476:
10000:
1820:
141:
3184:{\displaystyle \operatorname {Inf} _{i}^{\,(\rho )}=\operatorname {Stab} _{\rho }=\sum _{S\ni i}\rho ^{|S|-1}{\hat {f}}(S)^{2}.}
1090:
13309:
13097:
Bellare, Mihir; Coppersmith, Don; HĂĄstad, Johan; Kiwi, Marcos; Sudan, Madhu (1995). "Linearity testing in characteristic two".
13016:
12643:
2950:
1959:
1159:
13381:
12665:
11118:
is correlated with a Fourier character. Their proof relies on the following formula for the success probability of the test:
10435:{\displaystyle \left|\operatorname {E} _{x\sim \{-1,1\}^{n}}-\operatorname {E} _{g\sim N(0,I)}\right|=O(k9^{k}\varepsilon ).}
9526:
7481:{\displaystyle {\frac {d}{dp}}\operatorname {E} _{x\sim \mu _{p}}={\frac {\operatorname {Inf} }{p(1-p)}}=\sum _{i=1}^{n}\Pr.}
4971:{\displaystyle (T_{\rho }f)(x)=\operatorname {E} _{y\sim N_{\rho }(x)}=\sum _{S\subseteq }\rho ^{|S|}{\hat {f}}(S)\chi _{S}.}
5323:
11064:
Bellare et al. gave an extremely simple Fourier-analytic proof, that also shows that if the test succeeds with probability
5041:
12187:
8823:
5264:
4676:
4126:
2065:
1516:
556:
12939:
Ben-Or, Michael; Linial, Nathan (1985). "Collective coin flipping, robust voting schemes and minima of Banzhaf values".
10741:
7940:
13376:
8697:
8295:
12608:
in conjunction with an isoperimetric theorem of Borell in Gaussian space; since then more direct proofs were devised.
12407:
11235:
10609:
9310:
8820:
The Poincaré inequality for the Boolean cube (which follows from formulas appearing above) states that for a function
8628:
8226:
8079:
2940:
2936:'th coordinate, the value of the function changes. The average value of this quantity is exactly the total influence.
12761:
3548:{\displaystyle |\{i\in :\operatorname {Inf} _{i}^{\,(1-\delta )}\geq \epsilon \}|\leq {\frac {1}{\delta \epsilon }}.}
7250:
11222:
10986:
is linear then it always passes the test. Blum, Luby and Rubinfeld showed that if the test passes with probability
10486:
5720:
2524:
764:(Note that even if the function is 0-1 valued this is not a sum mod 2, but just an ordinary sum of real numbers.)
12814:
11511:
9669:
8393:
9419:
9289:{\displaystyle (x_{1,1}\land \cdots \land x_{1,w})\lor \cdots \lor (x_{2^{w},1}\land \cdots \land x_{2^{w},w}).}
7034:{\displaystyle y_{i}={\begin{cases}x_{i}&{\text{w.p. }}\rho ,\\z_{i}&{\text{w.p. }}1-\rho .\end{cases}}}
3371:
2618:
7801:
7247:
The Russo–Margulis formula (also called the Margulis–Russo formula) states that for monotone Boolean functions
4565:{\displaystyle \operatorname {NS} _{\delta }={\frac {1}{2}}-{\frac {1}{2}}\operatorname {Stab} _{1-2\delta }.}
3703:
2462:
12694:
1217:
12612:
116:) from a spectral perspective. The functions studied are often, but not always, Boolean-valued, making them
6794:{\displaystyle \operatorname {Inf} =\sum _{i=1}^{n}\operatorname {Inf} _{i}=\sum _{S}|S|{\hat {f}}(S)^{2}.}
5008:
2858:{\displaystyle \operatorname {Inf} =\sum _{i=1}^{n}\operatorname {Inf} _{i}=\sum _{S}|S|{\hat {f}}(S)^{2}.}
24:
12149:
11714:
5709:{\displaystyle \|T_{\rho }f\|_{q}\leq \|f\|_{2}\quad {\text{and}}\quad \|T_{\rho }f\|_{2}\leq \|f\|_{q'}.}
801:
754:{\displaystyle f(x)=\sum _{S\subseteq }{\hat {f}}(S)\chi _{S}(x),\quad \chi _{S}(x)=\prod _{i\in S}x_{i}.}
11599:
10856:
9845:
8467:
4397:
3778:
3600:
1592:
10492:
7759:
Many of the basic concepts of Fourier analysis on the Boolean cube have counterparts in Gaussian space:
6871:
5202:
4077:
3565:
12355:
12081:
12033:
9460:
11225:
states that for three and more candidates, the only unanimous voting rule for which there is always a
11067:
7706:
6832:
13321:
13113:
11035:
8766:
8364:
133:
13335:
13239:
10989:
10910:
10853:
we want to test whether a given function is linear. It is natural to try the following test: choose
10682:
8165:
is either constant, equal to a coordinate, or equal to the negation of a coordinate. In particular,
6965:
5232:
3968:
3877:
13371:
9660:
8955:{\displaystyle \operatorname {Var} \leq \operatorname {Inf} \leq \deg f\cdot \operatorname {Var} .}
1703:
835:
12982:
11747:
11669:
9931:
9780:
9506:
7660:
6653:{\displaystyle \operatorname {Inf} _{i}=\sum _{S\ni i}{\hat {f}}(S)^{2}=p(1-p)\operatorname {E} .}
5774:
5535:
3849:
according to one of the following two equivalent rules, applied independently to each coordinate:
1373:
1223:
932:
256:
155:
73:
12916:
Kahn, Jeff; Kalai, Gil; Linial, Nati (1988). "The influence of variables on Boolean functions.".
12620:
11803:
11471:
6084:
This measure can be generated by choosing each coordinate independently to be 1 with probability
5898:
5859:
298:
197:
113:
34:
13313:
12381:
9628:
8560:
4984:
13330:
13234:
13217:
12977:
12845:"Relationships between the number of inputs and other complexity measures of Boolean functions"
12594:{\displaystyle \operatorname {Stab} _{\rho }\leq 1-{\frac {2}{\pi }}\arccos \rho +\varepsilon }
10822:
6913:
5014:
4649:
901:
12020:{\displaystyle \operatorname {Stab} _{\rho }\longrightarrow 1-{\frac {2}{\pi }}\arccos \rho .}
10076:
9601:
7494:
5934:
481:
13025:
12874:
4618:
4453:
516:
11634:
11562:
11436:
5733:
5509:
12725:
12685:
12332:
12305:
10448:
9994:
9976:
9733:
8601:
8038:
7766:
6812:
5235:
4182:
3758:
3655:
3006:
125:
12733:
8:
13225:
11226:
9142:{\displaystyle \max _{i}\operatorname {Inf} _{i}=\Omega \left({\frac {\log n}{n}}\right)}
8012:
7791:
6107:
5724:
3677:
1741:
796:
9578:
Combined with the Russo–Margulis lemma, Friedgut's junta theorem implies that for every
5816:
13348:
13277:
13265:
13034:
12997:
12852:
12790:
12770:
12651:
12129:
11930:
11404:
11384:
11101:
11015:
10969:
10468:
9911:
9891:
9825:
9760:
9581:
9486:
9399:
9379:
9051:
9034:{\displaystyle \max _{i}\operatorname {Inf} _{i}\geq {\frac {\operatorname {Var} }{n}}}
8795:
8746:
8540:
8517:
8447:
8344:
8199:
8168:
8148:
7735:
7621:
7601:
7581:
7561:
7541:
7521:
6486:
6365:
6345:
6087:
5839:
5104:
5084:
4598:
4578:
4433:
3832:
2919:
2899:
2879:
2710:
2683:
2663:
2501:
2442:
2045:
1936:
1916:
1797:
1776:
1676:
1656:
1636:
1572:
1399:
881:
774:
768:
236:
13133:
12828:
12809:
10819:. It is not hard to show that the Boolean linear functions are exactly the characters
13082:
13065:
12713:
12661:
12302:
There are Boolean functions with larger noise stability. For example, a dictatorship
792:
13001:
12794:
12623:. This implication, due to Khot et al., was the impetus behind proving the theorem.
13352:
13340:
13287:
13244:
13196:
13161:
13128:
13077:
13044:
12987:
12944:
12921:
12862:
12823:
12810:"Boolean functions whose Fourier transform is concentrated on the first two levels"
12780:
12737:
12729:
12703:
10850:
7753:
7239:
Using this we can define the noise stability and the noise sensitivity, as before.
137:
117:
13201:
13182:
13166:
13149:
11947:
coordinates. Sheppard's formula gives the asymptotic noise stability of majority:
11207:{\displaystyle {\frac {1}{2}}+{\frac {1}{2}}\sum _{S\subseteq }{\hat {f}}(S)^{3}.}
9152:
The bound given by the Kahn–Kalai–Linial theorem is tight, and is achieved by the
13269:
12721:
8058:
Hypercontractivity holds (with appropriate parameters) in Gaussian space as well.
468:{\displaystyle f_{01}(x_{1},\ldots ,x_{n})=f((-1)^{x_{1}},\ldots ,(-1)^{x_{n}}).}
13049:
13020:
12681:
7641:
The Russo–Margulis formula is key for proving sharp threshold theorems such as
5771:
In many situations the input to the function is not uniformly distributed over
1494:{\displaystyle \operatorname {Var} =\sum _{S\neq \emptyset }{\hat {f}}(S)^{2}.}
1213:
13344:
13274:
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
13248:
13114:"A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem"
12785:
12756:
12708:
12689:
13365:
13270:"Noise stability on the Boolean hypercube via a renormalized Brownian motion"
13021:"Noise stability of functions with low influences: Invariance and optimality"
12968:
12717:
10586:
The invariance principle was the key ingredient in the original proof of the
7805:
2944:
121:
13314:"Optimal inapproximability results for MAX-CUT and other two-variable CSPs?"
13291:
12925:
5856:. In these situations it is customary to consider functions over the domain
13305:
11430:
1074:{\displaystyle \langle f,g\rangle =2^{-n}\sum _{x\in \{-1,1\}^{n}}f(x)g(x)}
129:
12964:"Boolean functions with low average sensitivity depend on few coordinates"
12741:
5184:{\displaystyle \operatorname {Stab} _{\rho }=\langle f,T_{\rho }f\rangle }
13261:
12948:
12616:
11790:
11367:{\displaystyle {\frac {3}{4}}-{\frac {3}{4}}\operatorname {Stab} _{-1/3}}
6471:
We can extend the definitions of influence and the noise operator to the
6074:{\displaystyle \mu _{p}(x)=p^{\sum _{i}x_{i}}(1-p)^{\sum _{i}(1-x_{i})}.}
929:, and they form an orthonormal basis for the space of all functions over
20:
11596:, is asymptotically smaller than the threshold itself, which is roughly
9457:
Friedgut's theorem is a converse to this result. It states that for any
1360:{\displaystyle \|f\|^{2}=\operatorname {E} =\sum _{S}{\hat {f}}(S)^{2}.}
12992:
12963:
11920:{\displaystyle \operatorname {Maj} _{n}\colon \{-1,1\}^{n}\to \{-1,1\}}
9822:
The invariance principle (in a special case) informally states that if
12866:
13039:
10175:{\displaystyle \varepsilon =\max _{i}\sum _{S\ni i}{\hat {f}}(S)^{2}}
5011:
in which each bit is flipped independently with rate 1. The operator
11401:
is a rule for which there is almost always a Condorcet winner, then
13282:
12857:
12656:
9819:
is close to a normal distribution with the same mean and variance.
7491:
Both the influence and the probabilities are taken with respect to
1084:
The Fourier coefficients can be calculated using an inner product:
12775:
8598:(a function depending on a constant number of coordinates), where
13066:"Self-testing/correcting with applications to numerical problems"
7930:{\displaystyle (U_{\rho }f)(x)=\operatorname {E} _{z\sim N(0,1)}}
513:-valued function, though often it is more convenient to consider
7518:, and on the right-hand side we have the average sensitivity of
5497:{\displaystyle \|f\|_{\infty }=\max _{x\in \{-1,1\}^{n}}|f(x)|.}
3437:
has at most “constantly” many “stably-influential” coordinates:
13014:
10242:{\displaystyle \sum _{S\neq \emptyset }{\hat {f}}(S)^{2}\leq 1}
5124:
Noise stability can be defined in terms of the noise operator:
13304:
12755:
Mossel, Elchanan; Oleszkiewicz, Krzysztof; Sen, Arnab (2013).
11744:. Here both the threshold window and the threshold itself are
11061:-close to a Fourier character. Their proof was combinatorial.
9598:, every monotone function is close to a junta with respect to
6461:{\displaystyle f=\sum _{S\subseteq }{\hat {f}}(S)\omega _{S}.}
11800:
implies that the width of threshold window is always at most
7657:, connects the distribution of functions on the Boolean cube
6663:
The total influence is the sum of the individual influences:
4788:{\displaystyle T_{\rho }f\colon \{-1,1\}^{n}\to \mathbb {R} }
13150:"Sharp thresholds of graph properties and the k-SAT problem"
13096:
9757:
is too large compared to the rest, then the distribution of
12690:"Logarithmic Sobolev inequalities for finite Markov chains"
12521:{\displaystyle \max _{i}\operatorname {Inf} _{i}\leq \tau }
10066:{\displaystyle f=\sum _{S\subseteq }{\hat {f}}(S)\chi _{S}}
7642:
7027:
4595:
is Boolean, then this is the probability that the value of
4057:
3939:
1903:{\displaystyle f^{=d}=\sum _{|S|=d}{\hat {f}}(S)\chi _{S}.}
13260:
12680:
1146:{\displaystyle {\hat {f}}(S)=\langle f,\chi _{S}\rangle .}
194:. Sometimes it is more convenient to work with the domain
6829:-correlated random variables can be obtained by choosing
2993:{\displaystyle \operatorname {Inf} =\langle f,Lf\rangle }
2027:{\displaystyle f^{>d},f^{<d},f^{\geq d},f^{\leq d}}
1696:
It is convenient to decompose the Fourier expansion into
1205:{\displaystyle {\hat {f}}(\emptyset )=\operatorname {E} }
152:
We will mostly consider functions defined on the domain
16:
Study of Boolean functions via discrete Fourier analysis
13064:
Blum, Manuel; Luby, Michael; Rubinfeld, Ronitt (1993).
9568:{\displaystyle \exp(\operatorname {Inf} /\varepsilon )}
5395:{\displaystyle \|f\|_{q}={\sqrt{\operatorname {E} }}.}
2868:
The total influence of a Boolean function is also the
13183:"Every monotone graph property has a sharp threshold"
12943:. SFCS'85. Portland, Oregon: IEEE. pp. 408–416.
12754:
12534:
12479:
12410:
12384:
12358:
12335:
12308:
12190:
12152:
12132:
12084:
12036:
12030:
This is related to the probability that if we choose
11956:
11933:
11857:
11806:
11750:
11717:
11672:
11637:
11602:
11565:
11514:
11474:
11439:
11407:
11387:
11307:
11238:
11127:
11104:
11070:
11038:
11018:
10992:
10972:
10913:
10859:
10825:
10744:
10685:
10612:
10495:
10471:
10451:
10258:
10188:
10111:
10079:
10003:
9979:
9934:
9914:
9894:
9848:
9828:
9783:
9763:
9736:
9672:
9666:
The Berry–Esseen theorem states (among else) that if
9631:
9604:
9584:
9529:
9509:
9489:
9463:
9422:
9402:
9382:
9313:
9165:
9074:
9054:
8971:
8885:
8826:
8798:
8769:
8749:
8700:
8631:
8604:
8563:
8543:
8520:
8470:
8450:
8396:
8367:
8347:
8298:
8229:
8202:
8171:
8151:
8082:
8041:
8015:
7943:
7814:
7769:
7738:
7709:
7663:
7624:
7604:
7584:
7564:
7544:
7524:
7497:
7319:
7253:
7053:
6946:
6916:
6874:
6835:
6815:
6672:
6512:
6489:
6475:-biased setting by using their spectral definitions.
6395:
6368:
6348:
6142:
6110:
6090:
5967:
5937:
5901:
5862:
5842:
5819:
5777:
5736:
5600:
5538:
5512:
5411:
5326:
5267:
5238:
5205:
5130:
5107:
5087:
5074:{\displaystyle {\frac {1}{2}}\log {\frac {1}{\rho }}}
5044:
5017:
4987:
4804:
4735:
4679:
4652:
4621:
4601:
4581:
4479:
4456:
4436:
4400:
4208:
4185:
4129:
4080:
3858:
3835:
3781:
3761:
3706:
3680:
3658:
3603:
3568:
3443:
3374:
3203:
3032:
3009:
2953:
2922:
2902:
2882:
2736:
2713:
2686:
2666:
2621:
2527:
2504:
2465:
2445:
2127:
2068:
2048:
1962:
1939:
1933:
by zeroing out all Fourier coefficients not on level
1919:
1823:
1800:
1779:
1744:
1706:
1679:
1659:
1639:
1595:
1575:
1519:
1425:
1402:
1376:
1271:
1226:
1162:
1093:
977:
935:
904:
884:
838:
804:
777:
618:
559:
519:
484:
343:
301:
259:
239:
200:
158:
76:
37:
12291:{\displaystyle \operatorname {Stab} _{\rho }=2\Pr-1}
8869:{\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }
5310:{\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }
4722:{\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }
4615:
changes if we flip each coordinate with probability
4172:{\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }
2111:{\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }
1562:{\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }
1504:
609:
has a unique expansion as a multilinear polynomial:
602:{\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }
13216:De, Anindya; Mossel, Elchanan; Neeman, Joe (2016),
13099:
Proc. 36th Symp. on Foundations of Computer Science
12941:
Proc. 26th Symp. on Foundations of Computer Science
12918:
Proc. 29th Symp. on Foundations of Computer Science
9842:is a multilinear polynomial of bounded degree over
8192:The Friedgut–Kalai–Naor theorem, also known as the
5506:The hypercontractivity theorem states that for any
12593:
12520:
12465:
12396:
12370:
12341:
12321:
12290:
12173:
12138:
12118:
12070:
12019:
11939:
11919:
11835:
11773:
11736:
11703:
11658:
11623:
11588:
11547:
11500:
11460:
11413:
11393:
11366:
11293:
11206:
11110:
11090:
11053:
11024:
11004:
10978:
10958:
10899:
10838:
10812:{\displaystyle xy=(x_{1}y_{1},\ldots ,x_{n}y_{n})}
10811:
10730:
10667:
10575:
10477:
10457:
10434:
10241:
10174:
10097:
10065:
9985:
9962:
9920:
9900:
9880:
9834:
9811:
9769:
9749:
9722:
9643:
9617:
9590:
9567:
9515:
9495:
9475:
9446:
9408:
9388:
9368:
9288:
9141:
9060:
9033:
8954:
8868:
8804:
8784:
8755:
8735:
8686:
8617:
8586:
8549:
8526:
8506:
8456:
8436:
8382:
8353:
8333:
8284:
8208:
8189:: a function depending on at most one coordinate.
8177:
8157:
8137:
8047:
8027:
8002:{\displaystyle (U_{\rho }f)(x)=\operatorname {E} }
8001:
7929:
7782:
7744:
7724:
7691:
7630:
7610:
7590:
7570:
7550:
7530:
7510:
7480:
7302:
7228:
7033:
6929:
6902:
6860:
6821:
6793:
6652:
6495:
6460:
6374:
6354:
6327:
6122:
6096:
6073:
5950:
5919:
5887:
5848:
5828:
5805:
5748:
5708:
5583:
5524:
5496:
5394:
5309:
5251:
5223:
5183:
5113:
5093:
5073:
5030:
4999:
4970:
4787:
4721:
4665:
4627:
4607:
4587:
4564:
4462:
4442:
4418:
4383:
4191:
4171:
4108:
4063:
3841:
3821:
3767:
3747:
3692:
3664:
3643:
3589:
3547:
3429:
3357:
3183:
3015:
2992:
2939:The total influence can also be defined using the
2928:
2908:
2888:
2857:
2719:
2692:
2672:
2652:
2604:
2510:
2490:
2451:
2428:
2110:
2054:
2026:
1945:
1925:
1902:
1806:
1785:
1760:
1730:
1685:
1665:
1645:
1625:
1581:
1561:
1493:
1408:
1388:
1359:
1254:
1204:
1145:
1073:
963:
917:
890:
862:
824:
783:
753:
601:
537:
505:
467:
326:
287:
245:
225:
186:
132:, and theoretical computer science, especially in
104:
62:
13276:. STOC. Orlando, Florida: ACM. pp. 661–671.
13063:
12807:
9044:The Kahn–Kalai–Linial theorem, also known as the
8736:{\displaystyle \|f^{>d}\|^{2}<\varepsilon }
8334:{\displaystyle \|f^{>1}\|^{2}<\varepsilon }
5007:, the noise operator can also be defined using a
13363:
13188:Proceedings of the American Mathematical Society
12808:Friedgut, Ehud; Kalai, Gil; Naor, Assaf (2002).
12481:
12466:{\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}
12226:
11559:: the width of the "threshold window", which is
11378:
11294:{\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}
10668:{\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}
10541:
10511:
10497:
10119:
9970:is close to its distribution in Gaussian space.
9369:{\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}
9076:
8973:
8687:{\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}
8537:Similarly, a Boolean function of degree at most
8471:
8285:{\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}
8138:{\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}
7447:
5432:
2553:
2518:'th coordinate flips the value of the function:
12920:. SFCS'88. White Plains: IEEE. pp. 68–80.
12915:
8792:-close to a Boolean function of degree at most
7578:varies, the derivative of the probability that
7558:as a property, then the formula states that as
3775:-correlated random variables by first choosing
13215:
11797:
8071:
7303:{\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}
2896:at a given point is the number of coordinates
13180:
12879:: CS1 maint: DOI inactive as of April 2024 (
12642:
7800:The counterpart of the noise operator is the
5719:Hypercontractivity is closely related to the
5038:corresponds to running this Markov chain for
2605:{\displaystyle \operatorname {Inf} _{i}=\Pr.}
295:, then the corresponding function defined on
13154:Journal of the American Mathematical Society
12938:
12638:
12636:
12460:
12445:
12433:
12417:
12107:
12091:
12059:
12043:
11914:
11899:
11887:
11871:
11288:
11273:
11261:
11245:
10888:
10872:
10662:
10647:
10635:
10619:
10291:
10275:
9951:
9935:
9800:
9784:
9363:
9348:
9336:
9320:
8849:
8833:
8815:
8718:
8701:
8681:
8666:
8654:
8638:
8410:
8397:
8316:
8299:
8279:
8264:
8252:
8236:
8132:
8117:
8105:
8089:
7680:
7664:
7653:One of the deepest results in the area, the
7297:
7285:
7273:
7260:
6312:
6281:
6231:
6200:
5876:
5863:
5794:
5778:
5689:
5682:
5670:
5653:
5637:
5630:
5618:
5601:
5458:
5442:
5419:
5412:
5334:
5327:
5290:
5274:
5178:
5156:
4768:
4752:
4702:
4686:
4152:
4136:
3810:
3794:
3632:
3616:
3516:
3449:
3424:
3409:
3397:
3381:
2987:
2972:
2091:
2075:
1542:
1526:
1279:
1272:
1243:
1227:
1137:
1118:
1036:
1020:
990:
978:
952:
936:
582:
566:
532:
520:
500:
485:
315:
302:
276:
260:
214:
201:
175:
159:
93:
77:
51:
38:
11548:{\displaystyle p\sim {\frac {\log n+c}{n}}}
9723:{\displaystyle f=\sum _{i=1}^{n}c_{i}x_{i}}
9302:
8437:{\displaystyle \|f-g\|^{2}=O(\varepsilon )}
1693:is its degree as a multilinear polynomial.
12613:Goemans–Williamson approximation algorithm
9447:{\displaystyle \operatorname {Inf} \leq M}
3430:{\displaystyle f:\{-1,1\}^{n}\to \{-1,1\}}
2653:{\displaystyle \operatorname {Inf} _{i}=0}
478:Similarly, for us a Boolean function is a
120:. The area has found many applications in
13334:
13281:
13238:
13200:
13165:
13132:
13081:
13048:
13038:
12991:
12981:
12856:
12827:
12784:
12774:
12707:
12655:
12633:
12605:
12604:The first proof of this theorem used the
11374:, from which the theorem easily follows.
10587:
10465:, this implies that the distributions of
9659:The invariance principle generalizes the
8862:
7712:
7654:
7242:
5303:
4781:
4715:
4165:
3480:
3043:
2104:
1555:
807:
595:
31:is the study of real-valued functions on
13218:"Majority is Stablest: Discrete and SoS"
13147:
12961:
9396:-junta (a function depending on at most
3755:. Concretely, we can generate a pair of
3748:{\displaystyle \operatorname {E} =\rho }
2491:{\displaystyle \operatorname {Inf} _{i}}
12893:
12842:
11846:
9654:
9523:-close to a Boolean junta depending on
4199:can be defined in two equivalent ways:
3829:uniformly at random, and then choosing
3003:A generalized form of influence is the
2118:can be defined in two equivalent ways:
112:(such functions are sometimes known as
13364:
12611:Majority is Stablest implies that the
11631:. In contrast, the probability that a
9454:according to the Poincaré inequality.
8223:to a dictatorship. Quantitatively, if
3194:The corresponding total influences is
13111:
8063:cube from results on Gaussian space.
5194:
2727:is the sum of all of its influences:
2498:is the probability that flipping the
874:, and the entire sum is known as the
12181:, then the majority stays the same:
12174:{\displaystyle {\frac {1-\rho }{2}}}
11737:{\displaystyle p\sim {\frac {c}{n}}}
11429:A classical result in the theory of
10907:uniformly at random, and check that
10601:
10596:
9908:are small, then the distribution of
7044:The noise operator is then given by
5763:
971:, with respect to the inner product
825:{\displaystyle \mathbb {Z} _{2}^{n}}
548:
13181:Friedgut, Ehud; Kalai, Gil (1996).
11666:graph contains a triangle tends to
11624:{\displaystyle {\frac {\log n}{n}}}
11468:random graph is connected tends to
11433:states that the probability that a
11424:
10900:{\displaystyle x,y\in \{-1,1\}^{n}}
9881:{\displaystyle x_{1},\ldots ,x_{n}}
8507:{\displaystyle \Pr=O(\varepsilon )}
8390:-close to a dictatorship, that is,
6804:
4419:{\displaystyle 0\leq \delta \leq 1}
3822:{\displaystyle x,z\in \{-1,1\}^{n}}
3644:{\displaystyle x,y\in \{-1,1\}^{n}}
1626:{\displaystyle {\hat {f}}(S)\neq 0}
13:
13308:; Kindler, Guy; Mossel, Elchanan;
13019:; Oleszkiewicz, Krzysztof (2010).
11751:
11217:
10576:{\displaystyle \sup _{t}|\Pr-\Pr|}
10336:
10265:
10200:
9110:
7975:
7847:
7618:equals the average sensitivity at
7336:
7171:
6903:{\displaystyle y\sim N_{\rho }(x)}
6603:
5423:
5349:
5224:{\displaystyle 1\leq q<\infty }
5218:
5101:, and taking the average value of
4837:
4235:
4109:{\displaystyle y\sim N_{\rho }(x)}
3707:
3590:{\displaystyle -1\leq \rho \leq 1}
3557:
3205:
3087:
2158:
1455:
1383:
1291:
1262:. Parseval's identity states that
1187:
1178:
14:
13393:
12903:Property testing, PCP, and juntas
12762:Geometric and Functional Analysis
12371:{\displaystyle \varepsilon >0}
12119:{\displaystyle y\in \{-1,1\}^{n}}
12071:{\displaystyle x\in \{-1,1\}^{n}}
10485:under both measures are close in
9476:{\displaystyle \varepsilon >0}
7648:
4673:is an operator taking a function
4638:
3674:if the marginal distributions of
3597:, we say that two random vectors
1505:Fourier degree and Fourier levels
147:
11927:denote the majority function on
11091:{\displaystyle 1/2+\varepsilon }
8066:
7725:{\displaystyle \mathbb {R} ^{n}}
6861:{\displaystyle x,z\sim \mu _{p}}
5813:, but instead has a bias toward
5721:logarithmic Sobolev inequalities
1673:. In other words, the degree of
13298:
13254:
13209:
13174:
13141:
13121:Advances in Applied Mathematics
13105:
13090:
13057:
13008:
12815:Advances in Applied Mathematics
12757:"On reverse hypercontractivity"
11054:{\displaystyle O(\varepsilon )}
9928:under the uniform measure over
9156:function of Ben-Or and Linial:
8785:{\displaystyle O(\varepsilon )}
8383:{\displaystyle O(\varepsilon )}
8055:-correlated standard Gaussians.
5652:
5646:
4729:and returning another function
4074:We denote this distribution by
3949:
3943:
3023:-stable influence, defined by:
1156:In particular, this shows that
699:
12955:
12932:
12909:
12905:(Thesis). Tel Aviv University.
12887:
12836:
12801:
12748:
12674:
12650:. Cambridge University Press.
12554:
12548:
12509:
12503:
12442:
12279:
12276:
12270:
12251:
12245:
12229:
12217:
12204:
11986:
11983:
11970:
11896:
11830:
11810:
11768:
11754:
11653:
11641:
11583:
11569:
11455:
11443:
11361:
11355:
11270:
11192:
11185:
11179:
11168:
11162:
11048:
11042:
11005:{\displaystyle 1-\varepsilon }
10959:{\displaystyle f(xy)=f(x)f(y)}
10953:
10947:
10941:
10935:
10926:
10917:
10806:
10754:
10731:{\displaystyle f(xy)=f(x)f(y)}
10725:
10719:
10713:
10707:
10698:
10689:
10644:
10569:
10565:
10556:
10550:
10544:
10535:
10526:
10520:
10514:
10507:
10426:
10407:
10393:
10390:
10387:
10381:
10375:
10369:
10361:
10349:
10329:
10326:
10323:
10317:
10311:
10305:
10224:
10217:
10211:
10163:
10156:
10150:
10050:
10044:
10038:
10027:
10021:
9562:
9551:
9545:
9536:
9435:
9429:
9345:
9280:
9222:
9210:
9166:
9104:
9098:
9022:
9016:
9001:
8995:
8946:
8940:
8916:
8910:
8898:
8892:
8858:
8779:
8773:
8663:
8514:for some Boolean dictatorship
8501:
8495:
8486:
8474:
8444:for some Boolean dictatorship
8431:
8425:
8377:
8371:
8261:
8114:
7996:
7993:
7987:
7981:
7969:
7963:
7960:
7944:
7924:
7921:
7886:
7880:
7872:
7860:
7840:
7834:
7831:
7815:
7472:
7450:
7417:
7405:
7397:
7391:
7376:
7373:
7367:
7361:
7282:
7220:
7217:
7211:
7205:
7197:
7191:
7164:
7158:
7145:
7139:
7133:
7121:
7113:
7102:
7096:
7079:
7073:
7070:
7054:
6897:
6891:
6779:
6772:
6766:
6756:
6748:
6731:
6725:
6685:
6679:
6644:
6635:
6612:
6609:
6600:
6588:
6573:
6566:
6560:
6532:
6526:
6478:
6442:
6436:
6430:
6419:
6413:
6316:
6277:
6235:
6196:
6159:
6153:
6063:
6044:
6030:
6017:
5984:
5978:
5578:
5558:
5487:
5483:
5477:
5470:
5378:
5368:
5359:
5355:
5299:
5150:
5144:
4952:
4946:
4940:
4928:
4920:
4909:
4903:
4886:
4883:
4877:
4871:
4863:
4857:
4830:
4824:
4821:
4805:
4777:
4711:
4556:
4550:
4499:
4493:
4369:
4362:
4356:
4344:
4336:
4325:
4319:
4302:
4299:
4293:
4287:
4281:
4275:
4267:
4261:
4228:
4222:
4161:
4103:
4097:
3736:
3713:
3520:
3507:
3501:
3493:
3481:
3464:
3458:
3445:
3406:
3368:One can prove that a function
3343:
3336:
3330:
3312:
3304:
3294:
3286:
3269:
3263:
3229:
3223:
3215:
3209:
3169:
3162:
3156:
3138:
3130:
3102:
3083:
3064:
3058:
3050:
3044:
2966:
2960:
2843:
2836:
2830:
2820:
2812:
2795:
2789:
2749:
2743:
2641:
2635:
2596:
2593:
2587:
2568:
2562:
2556:
2547:
2541:
2485:
2479:
2416:
2324:
2315:
2283:
2253:
2246:
2240:
2152:
2146:
2100:
1884:
1878:
1872:
1854:
1846:
1754:
1746:
1725:
1719:
1713:
1614:
1608:
1602:
1551:
1479:
1472:
1466:
1438:
1432:
1396:, then we get the variance of
1345:
1338:
1332:
1310:
1297:
1199:
1193:
1181:
1175:
1169:
1112:
1106:
1100:
1068:
1062:
1056:
1050:
857:
851:
845:
716:
710:
693:
687:
674:
668:
662:
651:
645:
628:
622:
591:
459:
443:
433:
408:
398:
395:
386:
354:
1:
13202:10.1090/S0002-9939-96-03732-X
13167:10.1090/S0894-0347-99-00305-7
13134:10.1016/S0196-8858(02)00023-4
12829:10.1016/S0196-8858(02)00024-6
12695:Annals of Applied Probability
12648:Analysis of Boolean functions
12626:
12078:uniformly at random and form
11223:Arrow's impossibility theorem
6342:-biased Fourier expansion of
1731:{\displaystyle {\hat {f}}(S)}
1216:is taken with respect to the
863:{\displaystyle {\hat {f}}(S)}
29:analysis of Boolean functions
13382:Theoretical computer science
13083:10.1016/0022-0000(93)90044-W
11774:{\displaystyle \Theta (1/n)}
11704:{\displaystyle e^{-c^{3}/6}}
11421:is close to a dictatorship.
9963:{\displaystyle \{-1,1\}^{n}}
9812:{\displaystyle \{-1,1\}^{n}}
9516:{\displaystyle \varepsilon }
7692:{\displaystyle \{-1,1\}^{n}}
5806:{\displaystyle \{-1,1\}^{n}}
5584:{\displaystyle q'=1/(1-1/q)}
5009:continuous-time Markov chain
2062:'th influence of a function
2037:
1389:{\displaystyle S=\emptyset }
1255:{\displaystyle \{-1,1\}^{n}}
964:{\displaystyle \{-1,1\}^{n}}
288:{\displaystyle \{-1,1\}^{n}}
187:{\displaystyle \{-1,1\}^{n}}
105:{\displaystyle \{-1,1\}^{n}}
25:theoretical computer science
7:
13050:10.4007/annals.2010.171.295
11836:{\displaystyle O(1/\log n)}
11501:{\displaystyle e^{-e^{-c}}}
8145:has degree at most 1, then
8072:Friedgut–Kalai–Naor theorem
7802:Ornstein–Uhlenbeck operator
6382:as a linear combination of
5920:{\displaystyle 0<p<1}
5888:{\displaystyle \{0,1\}^{n}}
553:Every real-valued function
545:-valued functions instead.
327:{\displaystyle \{0,1\}^{n}}
226:{\displaystyle \{0,1\}^{n}}
63:{\displaystyle \{0,1\}^{n}}
10:
13398:
12397:{\displaystyle \tau >0}
11789:analyze random graphs and
11555:. This is an example of a
9644:{\displaystyle q\approx p}
8587:{\displaystyle C_{W}2^{d}}
7732:endowed with the standard
5758:reverse hypercontractivity
5000:{\displaystyle \rho >0}
1700:: the Fourier coefficient
13377:Mathematical optimization
13345:10.1137/S0097539705447372
13322:SIAM Journal on Computing
13249:10.4086/toc.2016.v012a004
12786:10.1007/s00039-013-0229-4
12619:is optimal, assuming the
12473:has expectation zero and
10839:{\displaystyle \chi _{S}}
9663:to non-linear functions.
8816:Kahn–Kalai–Linial theorem
8594:coordinates, making it a
7699:to their distribution on
6930:{\displaystyle N_{\rho }}
6503:'s influence is given by
5031:{\displaystyle T_{\rho }}
4666:{\displaystyle T_{\rho }}
2916:such that if we flip the
918:{\displaystyle \chi _{S}}
134:hardness of approximation
12126:by flipping each bit of
10445:By choosing appropriate
10098:{\displaystyle k=\deg f}
9618:{\displaystyle \mu _{q}}
9303:Friedgut's junta theorem
8219:has degree 1 then it is
7511:{\displaystyle \mu _{p}}
5951:{\displaystyle \mu _{p}}
2947:, suitably normalized:
506:{\displaystyle \{-1,1\}}
114:pseudo-Boolean functions
13292:10.1145/3564246.3585118
13148:Friedgut, Ehud (1999).
12962:Friedgut, Ehud (1998).
12926:10.1109/SFCS.1988.21923
12709:10.1214/AOAP/1034968224
12621:unique games conjecture
11796:On a related note, the
6104:and 0 with probability
4628:{\displaystyle \delta }
4463:{\displaystyle \delta }
538:{\displaystyle \{0,1\}}
12869:(inactive 2024-04-25).
12843:Wellens, Jake (2020).
12595:
12522:
12467:
12398:
12372:
12343:
12323:
12292:
12175:
12140:
12120:
12072:
12021:
11941:
11921:
11837:
11775:
11738:
11705:
11660:
11659:{\displaystyle G(n,p)}
11625:
11590:
11589:{\displaystyle O(1/n)}
11549:
11502:
11462:
11461:{\displaystyle G(n,p)}
11415:
11395:
11368:
11295:
11208:
11112:
11092:
11055:
11026:
11006:
10980:
10960:
10901:
10840:
10813:
10732:
10669:
10577:
10479:
10459:
10436:
10243:
10176:
10099:
10067:
9987:
9964:
9922:
9902:
9888:and all influences of
9882:
9836:
9813:
9771:
9751:
9724:
9699:
9645:
9619:
9592:
9569:
9517:
9497:
9477:
9448:
9410:
9390:
9370:
9290:
9143:
9062:
9035:
8956:
8870:
8806:
8786:
8757:
8737:
8688:
8619:
8588:
8551:
8528:
8508:
8458:
8438:
8384:
8355:
8335:
8286:
8210:
8179:
8159:
8139:
8049:
8029:
8003:
7937:, or alternatively by
7931:
7784:
7746:
7726:
7693:
7632:
7612:
7592:
7572:
7552:
7532:
7512:
7482:
7446:
7304:
7243:Russo–Margulis formula
7230:
7035:
6931:
6904:
6862:
6823:
6795:
6711:
6654:
6497:
6462:
6376:
6356:
6329:
6124:
6098:
6075:
5952:
5921:
5889:
5850:
5830:
5807:
5750:
5749:{\displaystyle q<2}
5710:
5585:
5526:
5525:{\displaystyle q>2}
5498:
5396:
5311:
5253:
5225:
5185:
5115:
5095:
5075:
5032:
5001:
4972:
4789:
4723:
4667:
4629:
4609:
4589:
4566:
4464:
4444:
4420:
4385:
4193:
4173:
4110:
4065:
3843:
3823:
3769:
3749:
3694:
3666:
3645:
3591:
3549:
3431:
3359:
3185:
3017:
2994:
2930:
2910:
2890:
2876:of a Boolean function
2859:
2775:
2721:
2694:
2680:doesn't depend on the
2674:
2654:
2606:
2512:
2492:
2453:
2430:
2112:
2056:
2028:
1947:
1927:
1904:
1808:
1787:
1762:
1732:
1687:
1667:
1647:
1627:
1583:
1563:
1495:
1410:
1390:
1361:
1256:
1206:
1147:
1075:
965:
919:
892:
864:
826:
785:
755:
603:
539:
507:
469:
328:
289:
247:
227:
188:
106:
64:
13026:Annals of Mathematics
12894:Kindler, Guy (2002).
12596:
12523:
12468:
12399:
12373:
12344:
12342:{\displaystyle \rho }
12324:
12322:{\displaystyle x_{i}}
12293:
12176:
12141:
12121:
12073:
12022:
11942:
11922:
11838:
11776:
11739:
11706:
11661:
11626:
11591:
11550:
11503:
11463:
11416:
11396:
11369:
11296:
11209:
11113:
11093:
11056:
11027:
11007:
10981:
10961:
10902:
10841:
10814:
10733:
10670:
10578:
10480:
10460:
10458:{\displaystyle \psi }
10437:
10244:
10177:
10100:
10068:
9988:
9986:{\displaystyle \psi }
9965:
9923:
9903:
9883:
9837:
9814:
9772:
9752:
9750:{\displaystyle c_{i}}
9725:
9679:
9646:
9620:
9593:
9570:
9518:
9498:
9478:
9449:
9411:
9391:
9371:
9291:
9144:
9063:
9036:
8957:
8871:
8807:
8787:
8758:
8738:
8689:
8620:
8618:{\displaystyle C_{W}}
8589:
8552:
8529:
8509:
8459:
8439:
8385:
8356:
8336:
8287:
8211:
8180:
8160:
8140:
8050:
8048:{\displaystyle \rho }
8030:
8004:
7932:
7785:
7783:{\displaystyle L^{2}}
7747:
7727:
7703:, which is the space
7694:
7633:
7613:
7593:
7573:
7553:
7533:
7513:
7483:
7426:
7305:
7231:
7036:
6932:
6905:
6863:
6824:
6822:{\displaystyle \rho }
6796:
6691:
6655:
6498:
6463:
6377:
6357:
6330:
6125:
6099:
6076:
5953:
5922:
5890:
5851:
5831:
5808:
5751:
5730:A similar result for
5711:
5586:
5527:
5499:
5397:
5312:
5254:
5252:{\displaystyle L_{q}}
5226:
5186:
5116:
5096:
5076:
5033:
5002:
4973:
4790:
4724:
4668:
4630:
4610:
4590:
4567:
4465:
4445:
4421:
4386:
4194:
4192:{\displaystyle \rho }
4174:
4111:
4066:
3844:
3824:
3770:
3768:{\displaystyle \rho }
3750:
3695:
3667:
3665:{\displaystyle \rho }
3646:
3592:
3550:
3432:
3360:
3186:
3018:
3016:{\displaystyle \rho }
2995:
2931:
2911:
2891:
2872:of the function. The
2860:
2755:
2722:
2695:
2675:
2655:
2607:
2513:
2493:
2454:
2431:
2113:
2057:
2029:
1948:
1928:
1905:
1809:
1788:
1763:
1733:
1688:
1668:
1648:
1628:
1584:
1564:
1496:
1411:
1391:
1362:
1257:
1207:
1148:
1076:
966:
920:
893:
865:
827:
786:
756:
604:
540:
508:
470:
329:
290:
248:
228:
189:
107:
65:
13070:J. Comput. Syst. Sci
12949:10.1109/SFCS.1985.15
12606:invariance principle
12532:
12477:
12408:
12382:
12356:
12333:
12329:has noise stability
12306:
12188:
12150:
12130:
12082:
12034:
11954:
11931:
11855:
11847:Majority is stablest
11804:
11748:
11715:
11670:
11635:
11600:
11563:
11512:
11472:
11437:
11405:
11385:
11305:
11236:
11125:
11102:
11068:
11036:
11016:
10990:
10970:
10911:
10857:
10823:
10742:
10683:
10610:
10589:Majority is Stablest
10493:
10489:, which is given by
10469:
10449:
10256:
10186:
10109:
10077:
10001:
9977:
9932:
9912:
9892:
9846:
9826:
9781:
9761:
9734:
9670:
9661:Berry–Esseen theorem
9655:Invariance principle
9629:
9602:
9582:
9527:
9507:
9487:
9461:
9420:
9400:
9380:
9311:
9163:
9072:
9052:
8969:
8883:
8824:
8796:
8767:
8747:
8698:
8629:
8602:
8561:
8541:
8518:
8468:
8448:
8394:
8365:
8345:
8296:
8227:
8200:
8169:
8149:
8080:
8039:
8013:
7941:
7812:
7767:
7736:
7707:
7661:
7655:invariance principle
7622:
7602:
7582:
7562:
7542:
7522:
7495:
7317:
7251:
7051:
6944:
6914:
6872:
6833:
6813:
6670:
6510:
6487:
6393:
6386:-biased characters:
6366:
6362:is the expansion of
6346:
6140:
6108:
6088:
5965:
5935:
5899:
5860:
5840:
5817:
5775:
5734:
5598:
5536:
5510:
5409:
5324:
5265:
5236:
5203:
5128:
5105:
5085:
5042:
5015:
4985:
4802:
4733:
4677:
4650:
4619:
4599:
4579:
4477:
4454:
4434:
4398:
4206:
4183:
4127:
4078:
3856:
3833:
3779:
3759:
3704:
3678:
3656:
3601:
3566:
3441:
3372:
3201:
3030:
3007:
2951:
2920:
2900:
2880:
2734:
2711:
2684:
2664:
2619:
2525:
2502:
2463:
2443:
2125:
2066:
2046:
1960:
1956:We similarly define
1937:
1917:
1913:It is obtained from
1821:
1798:
1777:
1742:
1704:
1677:
1657:
1637:
1593:
1573:
1517:
1423:
1400:
1374:
1269:
1224:
1218:uniform distribution
1160:
1091:
975:
933:
902:
882:
872:Fourier coefficients
836:
802:
775:
616:
557:
517:
482:
341:
299:
257:
237:
198:
156:
126:social choice theory
74:
35:
13266:Raghavendra, Prasad
13264:; Mikulincer, Dan;
13226:Theory of Computing
13112:Kalai, Gil (2002).
11781:, and so this is a
11229:is a dictatorship.
10606:A Boolean function
9973:More formally, let
8557:depends on at most
8464:, or equivalently,
8028:{\displaystyle x,y}
7792:Hermite polynomials
6123:{\displaystyle 1-p}
5725:functional analysis
3693:{\displaystyle x,y}
3497:
3054:
2870:average sensitivity
1761:{\displaystyle |S|}
832:. The coefficients
821:
13015:Mossel, Elchanan;
12993:10.1007/PL00009809
12591:
12518:
12489:
12463:
12394:
12368:
12339:
12319:
12288:
12171:
12136:
12116:
12068:
12017:
11937:
11917:
11833:
11771:
11734:
11701:
11656:
11621:
11586:
11545:
11498:
11458:
11411:
11391:
11364:
11291:
11204:
11172:
11108:
11088:
11051:
11022:
11002:
10976:
10956:
10897:
10836:
10809:
10728:
10665:
10573:
10505:
10475:
10455:
10432:
10239:
10204:
10172:
10143:
10127:
10095:
10063:
10031:
9995:Lipschitz function
9983:
9960:
9918:
9898:
9878:
9832:
9809:
9767:
9747:
9720:
9641:
9615:
9588:
9565:
9513:
9493:
9473:
9444:
9416:coordinates) then
9406:
9386:
9366:
9286:
9139:
9084:
9058:
9031:
8981:
8965:This implies that
8952:
8866:
8802:
8782:
8753:
8733:
8684:
8615:
8584:
8547:
8524:
8504:
8454:
8434:
8380:
8351:
8331:
8282:
8206:
8175:
8155:
8135:
8045:
8025:
7999:
7927:
7790:) of multivariate
7780:
7742:
7722:
7689:
7628:
7608:
7588:
7568:
7548:
7528:
7508:
7478:
7300:
7226:
7106:
7031:
7026:
6927:
6900:
6868:independently and
6858:
6819:
6791:
6746:
6650:
6553:
6493:
6458:
6423:
6372:
6352:
6325:
6120:
6094:
6071:
6043:
6004:
5948:
5917:
5885:
5846:
5829:{\displaystyle -1}
5826:
5803:
5746:
5706:
5581:
5522:
5494:
5468:
5392:
5307:
5249:
5221:
5195:Hypercontractivity
5181:
5111:
5091:
5081:steps starting at
5071:
5028:
4997:
4968:
4913:
4785:
4719:
4663:
4625:
4605:
4585:
4562:
4460:
4440:
4416:
4381:
4329:
4189:
4169:
4106:
4061:
4056:
3938:
3839:
3819:
3765:
3745:
3690:
3662:
3641:
3587:
3545:
3470:
3427:
3355:
3284:
3181:
3123:
3033:
3013:
2990:
2941:discrete Laplacian
2926:
2906:
2886:
2855:
2810:
2717:
2690:
2670:
2650:
2602:
2508:
2488:
2449:
2426:
2424:
2233:
2108:
2052:
2024:
1943:
1923:
1900:
1865:
1804:
1783:
1758:
1728:
1683:
1663:
1643:
1623:
1579:
1559:
1491:
1459:
1406:
1386:
1357:
1325:
1252:
1202:
1143:
1071:
1046:
961:
927:Fourier characters
915:
888:
860:
822:
805:
781:
769:Hadamard transform
751:
737:
655:
599:
535:
503:
465:
324:
285:
243:
223:
184:
102:
60:
13195:(10): 2993–3002.
12867:10.19086/da.57741
12849:Discrete Analysis
12667:978-1-107-03832-5
12574:
12480:
12169:
12146:with probability
12139:{\displaystyle x}
12003:
11940:{\displaystyle n}
11732:
11619:
11543:
11414:{\displaystyle f}
11394:{\displaystyle f}
11329:
11316:
11182:
11151:
11149:
11136:
11111:{\displaystyle f}
11025:{\displaystyle f}
10979:{\displaystyle f}
10602:Linearity testing
10597:Some applications
10496:
10478:{\displaystyle f}
10214:
10189:
10153:
10128:
10118:
10041:
10010:
9921:{\displaystyle f}
9901:{\displaystyle f}
9835:{\displaystyle f}
9770:{\displaystyle f}
9591:{\displaystyle p}
9496:{\displaystyle f}
9409:{\displaystyle M}
9389:{\displaystyle M}
9133:
9075:
9061:{\displaystyle f}
9048:, states that if
9029:
8972:
8805:{\displaystyle d}
8756:{\displaystyle f}
8550:{\displaystyle d}
8527:{\displaystyle g}
8457:{\displaystyle g}
8354:{\displaystyle f}
8209:{\displaystyle f}
8196:, states that if
8178:{\displaystyle f}
8158:{\displaystyle f}
7916:
7745:{\displaystyle n}
7631:{\displaystyle p}
7611:{\displaystyle p}
7591:{\displaystyle f}
7571:{\displaystyle p}
7551:{\displaystyle f}
7538:. If we think of
7531:{\displaystyle f}
7421:
7333:
7136:
7085:
7010:
6983:
6769:
6737:
6563:
6538:
6496:{\displaystyle i}
6433:
6402:
6375:{\displaystyle f}
6355:{\displaystyle f}
6268:
6267:
6188:
6187:
6097:{\displaystyle p}
6034:
5995:
5849:{\displaystyle 1}
5650:
5431:
5387:
5114:{\displaystyle f}
5094:{\displaystyle x}
5069:
5053:
4943:
4892:
4635:, independently.
4608:{\displaystyle f}
4588:{\displaystyle f}
4526:
4513:
4443:{\displaystyle f}
4428:noise sensitivity
4359:
4308:
4049:
4031:
4004:
3986:
3947:
3922:
3895:
3842:{\displaystyle y}
3700:are uniform, and
3540:
3333:
3275:
3248:
3159:
3108:
2929:{\displaystyle i}
2909:{\displaystyle i}
2889:{\displaystyle f}
2833:
2801:
2720:{\displaystyle f}
2693:{\displaystyle i}
2673:{\displaystyle f}
2511:{\displaystyle i}
2452:{\displaystyle f}
2243:
2218:
2199:
2055:{\displaystyle i}
1946:{\displaystyle d}
1926:{\displaystyle f}
1875:
1840:
1807:{\displaystyle f}
1786:{\displaystyle d}
1716:
1686:{\displaystyle f}
1666:{\displaystyle d}
1646:{\displaystyle S}
1605:
1582:{\displaystyle d}
1469:
1444:
1409:{\displaystyle f}
1335:
1316:
1172:
1103:
1009:
891:{\displaystyle f}
876:Fourier expansion
848:
793:Fourier transform
784:{\displaystyle f}
722:
665:
634:
549:Fourier expansion
246:{\displaystyle f}
118:Boolean functions
13389:
13356:
13355:
13338:
13318:
13302:
13296:
13295:
13285:
13258:
13252:
13251:
13242:
13222:
13213:
13207:
13206:
13204:
13178:
13172:
13171:
13169:
13160:(4): 1017–1054.
13145:
13139:
13138:
13136:
13118:
13109:
13103:
13102:
13094:
13088:
13087:
13085:
13061:
13055:
13054:
13052:
13042:
13012:
13006:
13005:
12995:
12985:
12959:
12953:
12952:
12936:
12930:
12929:
12913:
12907:
12906:
12900:
12891:
12885:
12884:
12878:
12870:
12860:
12840:
12834:
12833:
12831:
12805:
12799:
12798:
12788:
12778:
12769:(3): 1062–1097.
12752:
12746:
12745:
12711:
12678:
12672:
12671:
12659:
12640:
12600:
12598:
12597:
12592:
12575:
12567:
12544:
12543:
12527:
12525:
12524:
12519:
12499:
12498:
12488:
12472:
12470:
12469:
12464:
12441:
12440:
12403:
12401:
12400:
12395:
12377:
12375:
12374:
12369:
12348:
12346:
12345:
12340:
12328:
12326:
12325:
12320:
12318:
12317:
12297:
12295:
12294:
12289:
12266:
12265:
12241:
12240:
12216:
12215:
12200:
12199:
12180:
12178:
12177:
12172:
12170:
12165:
12154:
12145:
12143:
12142:
12137:
12125:
12123:
12122:
12117:
12115:
12114:
12077:
12075:
12074:
12069:
12067:
12066:
12026:
12024:
12023:
12018:
12004:
11996:
11982:
11981:
11966:
11965:
11946:
11944:
11943:
11938:
11926:
11924:
11923:
11918:
11895:
11894:
11867:
11866:
11842:
11840:
11839:
11834:
11820:
11783:coarse threshold
11780:
11778:
11777:
11772:
11764:
11743:
11741:
11740:
11735:
11733:
11725:
11710:
11708:
11707:
11702:
11700:
11699:
11695:
11690:
11689:
11665:
11663:
11662:
11657:
11630:
11628:
11627:
11622:
11620:
11615:
11604:
11595:
11593:
11592:
11587:
11579:
11554:
11552:
11551:
11546:
11544:
11539:
11522:
11507:
11505:
11504:
11499:
11497:
11496:
11495:
11494:
11467:
11465:
11464:
11459:
11425:Sharp thresholds
11420:
11418:
11417:
11412:
11400:
11398:
11397:
11392:
11381:implies that if
11373:
11371:
11370:
11365:
11351:
11350:
11346:
11330:
11322:
11317:
11309:
11300:
11298:
11297:
11292:
11269:
11268:
11227:Condorcet winner
11213:
11211:
11210:
11205:
11200:
11199:
11184:
11183:
11175:
11171:
11150:
11142:
11137:
11129:
11117:
11115:
11114:
11109:
11097:
11095:
11094:
11089:
11078:
11060:
11058:
11057:
11052:
11031:
11029:
11028:
11023:
11011:
11009:
11008:
11003:
10985:
10983:
10982:
10977:
10965:
10963:
10962:
10957:
10906:
10904:
10903:
10898:
10896:
10895:
10851:property testing
10845:
10843:
10842:
10837:
10835:
10834:
10818:
10816:
10815:
10810:
10805:
10804:
10795:
10794:
10776:
10775:
10766:
10765:
10737:
10735:
10734:
10729:
10679:if it satisfies
10674:
10672:
10671:
10666:
10643:
10642:
10582:
10580:
10579:
10574:
10572:
10510:
10504:
10484:
10482:
10481:
10476:
10464:
10462:
10461:
10456:
10441:
10439:
10438:
10433:
10422:
10421:
10400:
10396:
10365:
10364:
10301:
10300:
10299:
10298:
10248:
10246:
10245:
10240:
10232:
10231:
10216:
10215:
10207:
10203:
10181:
10179:
10178:
10173:
10171:
10170:
10155:
10154:
10146:
10142:
10126:
10104:
10102:
10101:
10096:
10072:
10070:
10069:
10064:
10062:
10061:
10043:
10042:
10034:
10030:
9993:be a univariate
9992:
9990:
9989:
9984:
9969:
9967:
9966:
9961:
9959:
9958:
9927:
9925:
9924:
9919:
9907:
9905:
9904:
9899:
9887:
9885:
9884:
9879:
9877:
9876:
9858:
9857:
9841:
9839:
9838:
9833:
9818:
9816:
9815:
9810:
9808:
9807:
9776:
9774:
9773:
9768:
9756:
9754:
9753:
9748:
9746:
9745:
9729:
9727:
9726:
9721:
9719:
9718:
9709:
9708:
9698:
9693:
9650:
9648:
9647:
9642:
9624:
9622:
9621:
9616:
9614:
9613:
9597:
9595:
9594:
9589:
9574:
9572:
9571:
9566:
9558:
9522:
9520:
9519:
9514:
9502:
9500:
9499:
9494:
9482:
9480:
9479:
9474:
9453:
9451:
9450:
9445:
9415:
9413:
9412:
9407:
9395:
9393:
9392:
9387:
9375:
9373:
9372:
9367:
9344:
9343:
9295:
9293:
9292:
9287:
9279:
9278:
9271:
9270:
9247:
9246:
9239:
9238:
9209:
9208:
9184:
9183:
9148:
9146:
9145:
9140:
9138:
9134:
9129:
9118:
9094:
9093:
9083:
9068:is Boolean then
9067:
9065:
9064:
9059:
9040:
9038:
9037:
9032:
9030:
9025:
9008:
8991:
8990:
8980:
8961:
8959:
8958:
8953:
8875:
8873:
8872:
8867:
8865:
8857:
8856:
8811:
8809:
8808:
8803:
8791:
8789:
8788:
8783:
8762:
8760:
8759:
8754:
8742:
8740:
8739:
8734:
8726:
8725:
8716:
8715:
8693:
8691:
8690:
8685:
8662:
8661:
8624:
8622:
8621:
8616:
8614:
8613:
8593:
8591:
8590:
8585:
8583:
8582:
8573:
8572:
8556:
8554:
8553:
8548:
8533:
8531:
8530:
8525:
8513:
8511:
8510:
8505:
8463:
8461:
8460:
8455:
8443:
8441:
8440:
8435:
8418:
8417:
8389:
8387:
8386:
8381:
8360:
8358:
8357:
8352:
8340:
8338:
8337:
8332:
8324:
8323:
8314:
8313:
8291:
8289:
8288:
8283:
8260:
8259:
8215:
8213:
8212:
8207:
8184:
8182:
8181:
8176:
8164:
8162:
8161:
8156:
8144:
8142:
8141:
8136:
8113:
8112:
8054:
8052:
8051:
8046:
8034:
8032:
8031:
8026:
8008:
8006:
8005:
8000:
7956:
7955:
7936:
7934:
7933:
7928:
7917:
7915:
7914:
7899:
7876:
7875:
7827:
7826:
7806:Mehler transform
7804:(related to the
7789:
7787:
7786:
7781:
7779:
7778:
7754:Gaussian measure
7751:
7749:
7748:
7743:
7731:
7729:
7728:
7723:
7721:
7720:
7715:
7698:
7696:
7695:
7690:
7688:
7687:
7637:
7635:
7634:
7629:
7617:
7615:
7614:
7609:
7597:
7595:
7594:
7589:
7577:
7575:
7574:
7569:
7557:
7555:
7554:
7549:
7537:
7535:
7534:
7529:
7517:
7515:
7514:
7509:
7507:
7506:
7487:
7485:
7484:
7479:
7471:
7470:
7445:
7440:
7422:
7420:
7400:
7383:
7357:
7356:
7355:
7354:
7334:
7332:
7321:
7309:
7307:
7306:
7301:
7281:
7280:
7235:
7233:
7232:
7227:
7201:
7200:
7190:
7189:
7157:
7156:
7138:
7137:
7129:
7126:
7125:
7124:
7116:
7105:
7066:
7065:
7040:
7038:
7037:
7032:
7030:
7029:
7011:
7008:
7004:
7003:
6984:
6981:
6977:
6976:
6956:
6955:
6936:
6934:
6933:
6928:
6926:
6925:
6909:
6907:
6906:
6901:
6890:
6889:
6867:
6865:
6864:
6859:
6857:
6856:
6828:
6826:
6825:
6820:
6800:
6798:
6797:
6792:
6787:
6786:
6771:
6770:
6762:
6759:
6751:
6745:
6721:
6720:
6710:
6705:
6659:
6657:
6656:
6651:
6643:
6642:
6633:
6632:
6581:
6580:
6565:
6564:
6556:
6552:
6522:
6521:
6502:
6500:
6499:
6494:
6467:
6465:
6464:
6459:
6454:
6453:
6435:
6434:
6426:
6422:
6381:
6379:
6378:
6373:
6361:
6359:
6358:
6353:
6334:
6332:
6331:
6326:
6321:
6320:
6319:
6305:
6304:
6280:
6274:
6270:
6269:
6263:
6252:
6251:
6240:
6239:
6238:
6224:
6223:
6199:
6193:
6189:
6186:
6172:
6171:
6152:
6151:
6129:
6127:
6126:
6121:
6103:
6101:
6100:
6095:
6080:
6078:
6077:
6072:
6067:
6066:
6062:
6061:
6042:
6016:
6015:
6014:
6013:
6003:
5977:
5976:
5957:
5955:
5954:
5949:
5947:
5946:
5931:-biased measure
5926:
5924:
5923:
5918:
5894:
5892:
5891:
5886:
5884:
5883:
5855:
5853:
5852:
5847:
5835:
5833:
5832:
5827:
5812:
5810:
5809:
5804:
5802:
5801:
5767:-Biased analysis
5755:
5753:
5752:
5747:
5715:
5713:
5712:
5707:
5702:
5701:
5700:
5678:
5677:
5665:
5664:
5651:
5648:
5645:
5644:
5626:
5625:
5613:
5612:
5590:
5588:
5587:
5582:
5574:
5557:
5546:
5531:
5529:
5528:
5523:
5503:
5501:
5500:
5495:
5490:
5473:
5467:
5466:
5465:
5427:
5426:
5401:
5399:
5398:
5393:
5388:
5386:
5381:
5377:
5376:
5371:
5362:
5347:
5342:
5341:
5316:
5314:
5313:
5308:
5306:
5298:
5297:
5258:
5256:
5255:
5250:
5248:
5247:
5230:
5228:
5227:
5222:
5190:
5188:
5187:
5182:
5174:
5173:
5140:
5139:
5120:
5118:
5117:
5112:
5100:
5098:
5097:
5092:
5080:
5078:
5077:
5072:
5070:
5062:
5054:
5046:
5037:
5035:
5034:
5029:
5027:
5026:
5006:
5004:
5003:
4998:
4977:
4975:
4974:
4969:
4964:
4963:
4945:
4944:
4936:
4933:
4932:
4931:
4923:
4912:
4867:
4866:
4856:
4855:
4817:
4816:
4794:
4792:
4791:
4786:
4784:
4776:
4775:
4745:
4744:
4728:
4726:
4725:
4720:
4718:
4710:
4709:
4672:
4670:
4669:
4664:
4662:
4661:
4634:
4632:
4631:
4626:
4614:
4612:
4611:
4606:
4594:
4592:
4591:
4586:
4571:
4569:
4568:
4563:
4546:
4545:
4527:
4519:
4514:
4506:
4489:
4488:
4469:
4467:
4466:
4461:
4449:
4447:
4446:
4441:
4425:
4423:
4422:
4417:
4390:
4388:
4387:
4382:
4377:
4376:
4361:
4360:
4352:
4349:
4348:
4347:
4339:
4328:
4271:
4270:
4260:
4259:
4218:
4217:
4198:
4196:
4195:
4190:
4178:
4176:
4175:
4170:
4168:
4160:
4159:
4115:
4113:
4112:
4107:
4096:
4095:
4070:
4068:
4067:
4062:
4060:
4059:
4050:
4045:
4034:
4032:
4029:
4025:
4024:
4005:
4000:
3989:
3987:
3984:
3980:
3979:
3959:
3958:
3948:
3945:
3942:
3941:
3923:
3920:
3916:
3915:
3896:
3893:
3889:
3888:
3868:
3867:
3848:
3846:
3845:
3840:
3828:
3826:
3825:
3820:
3818:
3817:
3774:
3772:
3771:
3766:
3754:
3752:
3751:
3746:
3735:
3734:
3725:
3724:
3699:
3697:
3696:
3691:
3671:
3669:
3668:
3663:
3650:
3648:
3647:
3642:
3640:
3639:
3596:
3594:
3593:
3588:
3554:
3552:
3551:
3546:
3541:
3539:
3528:
3523:
3496:
3478:
3448:
3436:
3434:
3433:
3428:
3405:
3404:
3364:
3362:
3361:
3356:
3351:
3350:
3335:
3334:
3326:
3323:
3322:
3315:
3307:
3297:
3289:
3283:
3259:
3258:
3249:
3247:
3236:
3219:
3218:
3190:
3188:
3187:
3182:
3177:
3176:
3161:
3160:
3152:
3149:
3148:
3141:
3133:
3122:
3095:
3094:
3079:
3078:
3053:
3041:
3022:
3020:
3019:
3014:
2999:
2997:
2996:
2991:
2935:
2933:
2932:
2927:
2915:
2913:
2912:
2907:
2895:
2893:
2892:
2887:
2864:
2862:
2861:
2856:
2851:
2850:
2835:
2834:
2826:
2823:
2815:
2809:
2785:
2784:
2774:
2769:
2726:
2724:
2723:
2718:
2700:'th coordinate.
2699:
2697:
2696:
2691:
2679:
2677:
2676:
2671:
2659:
2657:
2656:
2651:
2631:
2630:
2611:
2609:
2608:
2603:
2586:
2585:
2537:
2536:
2517:
2515:
2514:
2509:
2497:
2495:
2494:
2489:
2475:
2474:
2459:is Boolean then
2458:
2456:
2455:
2450:
2435:
2433:
2432:
2427:
2425:
2415:
2414:
2396:
2395:
2377:
2376:
2361:
2360:
2336:
2335:
2314:
2313:
2295:
2294:
2282:
2281:
2268:
2261:
2260:
2245:
2244:
2236:
2232:
2214:
2210:
2209:
2204:
2200:
2195:
2194:
2193:
2174:
2142:
2141:
2131:
2117:
2115:
2114:
2109:
2107:
2099:
2098:
2061:
2059:
2058:
2053:
2033:
2031:
2030:
2025:
2023:
2022:
2007:
2006:
1991:
1990:
1975:
1974:
1952:
1950:
1949:
1944:
1932:
1930:
1929:
1924:
1909:
1907:
1906:
1901:
1896:
1895:
1877:
1876:
1868:
1864:
1857:
1849:
1836:
1835:
1813:
1811:
1810:
1805:
1792:
1790:
1789:
1784:
1767:
1765:
1764:
1759:
1757:
1749:
1737:
1735:
1734:
1729:
1718:
1717:
1709:
1692:
1690:
1689:
1684:
1672:
1670:
1669:
1664:
1652:
1650:
1649:
1644:
1632:
1630:
1629:
1624:
1607:
1606:
1598:
1588:
1586:
1585:
1580:
1568:
1566:
1565:
1560:
1558:
1550:
1549:
1500:
1498:
1497:
1492:
1487:
1486:
1471:
1470:
1462:
1458:
1415:
1413:
1412:
1407:
1395:
1393:
1392:
1387:
1366:
1364:
1363:
1358:
1353:
1352:
1337:
1336:
1328:
1324:
1309:
1308:
1287:
1286:
1261:
1259:
1258:
1253:
1251:
1250:
1211:
1209:
1208:
1203:
1174:
1173:
1165:
1152:
1150:
1149:
1144:
1136:
1135:
1105:
1104:
1096:
1080:
1078:
1077:
1072:
1045:
1044:
1043:
1008:
1007:
970:
968:
967:
962:
960:
959:
924:
922:
921:
916:
914:
913:
898:. The functions
897:
895:
894:
889:
869:
867:
866:
861:
850:
849:
841:
831:
829:
828:
823:
820:
815:
810:
790:
788:
787:
782:
771:of the function
760:
758:
757:
752:
747:
746:
736:
709:
708:
686:
685:
667:
666:
658:
654:
608:
606:
605:
600:
598:
590:
589:
544:
542:
541:
536:
512:
510:
509:
504:
474:
472:
471:
466:
458:
457:
456:
455:
423:
422:
421:
420:
385:
384:
366:
365:
353:
352:
333:
331:
330:
325:
323:
322:
294:
292:
291:
286:
284:
283:
252:
250:
249:
244:
232:
230:
229:
224:
222:
221:
193:
191:
190:
185:
183:
182:
138:property testing
111:
109:
108:
103:
101:
100:
69:
67:
66:
61:
59:
58:
13397:
13396:
13392:
13391:
13390:
13388:
13387:
13386:
13372:Boolean algebra
13362:
13361:
13360:
13359:
13336:10.1.1.130.8886
13316:
13310:O'Donnell, Ryan
13303:
13299:
13259:
13255:
13240:10.1.1.757.3048
13220:
13214:
13210:
13179:
13175:
13146:
13142:
13116:
13110:
13106:
13095:
13091:
13062:
13058:
13017:O'Donnell, Ryan
13013:
13009:
12960:
12956:
12937:
12933:
12914:
12910:
12898:
12892:
12888:
12872:
12871:
12841:
12837:
12806:
12802:
12753:
12749:
12688:(August 1996).
12686:L. Saloff-Coste
12679:
12675:
12668:
12644:O'Donnell, Ryan
12641:
12634:
12629:
12566:
12539:
12535:
12533:
12530:
12529:
12494:
12490:
12484:
12478:
12475:
12474:
12436:
12432:
12409:
12406:
12405:
12383:
12380:
12379:
12357:
12354:
12353:
12334:
12331:
12330:
12313:
12309:
12307:
12304:
12303:
12261:
12257:
12236:
12232:
12211:
12207:
12195:
12191:
12189:
12186:
12185:
12155:
12153:
12151:
12148:
12147:
12131:
12128:
12127:
12110:
12106:
12083:
12080:
12079:
12062:
12058:
12035:
12032:
12031:
11995:
11977:
11973:
11961:
11957:
11955:
11952:
11951:
11932:
11929:
11928:
11890:
11886:
11862:
11858:
11856:
11853:
11852:
11849:
11816:
11805:
11802:
11801:
11760:
11749:
11746:
11745:
11724:
11716:
11713:
11712:
11691:
11685:
11681:
11677:
11673:
11671:
11668:
11667:
11636:
11633:
11632:
11605:
11603:
11601:
11598:
11597:
11575:
11564:
11561:
11560:
11557:sharp threshold
11523:
11521:
11513:
11510:
11509:
11487:
11483:
11479:
11475:
11473:
11470:
11469:
11438:
11435:
11434:
11427:
11406:
11403:
11402:
11386:
11383:
11382:
11342:
11335:
11331:
11321:
11308:
11306:
11303:
11302:
11264:
11260:
11237:
11234:
11233:
11220:
11218:Arrow's theorem
11195:
11191:
11174:
11173:
11155:
11141:
11128:
11126:
11123:
11122:
11103:
11100:
11099:
11074:
11069:
11066:
11065:
11037:
11034:
11033:
11017:
11014:
11013:
10991:
10988:
10987:
10971:
10968:
10967:
10912:
10909:
10908:
10891:
10887:
10858:
10855:
10854:
10830:
10826:
10824:
10821:
10820:
10800:
10796:
10790:
10786:
10771:
10767:
10761:
10757:
10743:
10740:
10739:
10684:
10681:
10680:
10638:
10634:
10611:
10608:
10607:
10604:
10599:
10568:
10506:
10500:
10494:
10491:
10490:
10470:
10467:
10466:
10450:
10447:
10446:
10417:
10413:
10339:
10335:
10294:
10290:
10268:
10264:
10263:
10259:
10257:
10254:
10253:
10227:
10223:
10206:
10205:
10193:
10187:
10184:
10183:
10182:. Suppose that
10166:
10162:
10145:
10144:
10132:
10122:
10110:
10107:
10106:
10078:
10075:
10074:
10057:
10053:
10033:
10032:
10014:
10002:
9999:
9998:
9978:
9975:
9974:
9954:
9950:
9933:
9930:
9929:
9913:
9910:
9909:
9893:
9890:
9889:
9872:
9868:
9853:
9849:
9847:
9844:
9843:
9827:
9824:
9823:
9803:
9799:
9782:
9779:
9778:
9762:
9759:
9758:
9741:
9737:
9735:
9732:
9731:
9714:
9710:
9704:
9700:
9694:
9683:
9671:
9668:
9667:
9657:
9630:
9627:
9626:
9609:
9605:
9603:
9600:
9599:
9583:
9580:
9579:
9554:
9528:
9525:
9524:
9508:
9505:
9504:
9488:
9485:
9484:
9483:, the function
9462:
9459:
9458:
9421:
9418:
9417:
9401:
9398:
9397:
9381:
9378:
9377:
9339:
9335:
9312:
9309:
9308:
9305:
9266:
9262:
9261:
9257:
9234:
9230:
9229:
9225:
9198:
9194:
9173:
9169:
9164:
9161:
9160:
9119:
9117:
9113:
9089:
9085:
9079:
9073:
9070:
9069:
9053:
9050:
9049:
9009:
9007:
8986:
8982:
8976:
8970:
8967:
8966:
8884:
8881:
8880:
8861:
8852:
8848:
8825:
8822:
8821:
8818:
8797:
8794:
8793:
8768:
8765:
8764:
8748:
8745:
8744:
8721:
8717:
8708:
8704:
8699:
8696:
8695:
8657:
8653:
8630:
8627:
8626:
8609:
8605:
8603:
8600:
8599:
8578:
8574:
8568:
8564:
8562:
8559:
8558:
8542:
8539:
8538:
8519:
8516:
8515:
8469:
8466:
8465:
8449:
8446:
8445:
8413:
8409:
8395:
8392:
8391:
8366:
8363:
8362:
8346:
8343:
8342:
8319:
8315:
8306:
8302:
8297:
8294:
8293:
8255:
8251:
8228:
8225:
8224:
8201:
8198:
8197:
8170:
8167:
8166:
8150:
8147:
8146:
8108:
8104:
8081:
8078:
8077:
8074:
8069:
8040:
8037:
8036:
8014:
8011:
8010:
7951:
7947:
7942:
7939:
7938:
7910:
7906:
7898:
7850:
7846:
7822:
7818:
7813:
7810:
7809:
7774:
7770:
7768:
7765:
7764:
7737:
7734:
7733:
7716:
7711:
7710:
7708:
7705:
7704:
7683:
7679:
7662:
7659:
7658:
7651:
7623:
7620:
7619:
7603:
7600:
7599:
7583:
7580:
7579:
7563:
7560:
7559:
7543:
7540:
7539:
7523:
7520:
7519:
7502:
7498:
7496:
7493:
7492:
7463:
7459:
7441:
7430:
7401:
7384:
7382:
7350:
7346:
7339:
7335:
7325:
7320:
7318:
7315:
7314:
7276:
7272:
7252:
7249:
7248:
7245:
7185:
7181:
7174:
7170:
7152:
7148:
7128:
7127:
7120:
7112:
7111:
7107:
7089:
7061:
7057:
7052:
7049:
7048:
7025:
7024:
7007:
7005:
6999:
6995:
6992:
6991:
6980:
6978:
6972:
6968:
6961:
6960:
6951:
6947:
6945:
6942:
6941:
6921:
6917:
6915:
6912:
6911:
6885:
6881:
6873:
6870:
6869:
6852:
6848:
6834:
6831:
6830:
6814:
6811:
6810:
6807:
6782:
6778:
6761:
6760:
6755:
6747:
6741:
6716:
6712:
6706:
6695:
6671:
6668:
6667:
6638:
6634:
6625:
6621:
6576:
6572:
6555:
6554:
6542:
6517:
6513:
6511:
6508:
6507:
6488:
6485:
6484:
6481:
6449:
6445:
6425:
6424:
6406:
6394:
6391:
6390:
6367:
6364:
6363:
6347:
6344:
6343:
6315:
6300:
6296:
6276:
6275:
6253:
6250:
6246:
6242:
6241:
6234:
6219:
6215:
6195:
6194:
6176:
6170:
6166:
6165:
6147:
6143:
6141:
6138:
6137:
6109:
6106:
6105:
6089:
6086:
6085:
6057:
6053:
6038:
6033:
6029:
6009:
6005:
5999:
5994:
5990:
5972:
5968:
5966:
5963:
5962:
5942:
5938:
5936:
5933:
5932:
5900:
5897:
5896:
5879:
5875:
5861:
5858:
5857:
5841:
5838:
5837:
5818:
5815:
5814:
5797:
5793:
5776:
5773:
5772:
5769:
5735:
5732:
5731:
5693:
5692:
5688:
5673:
5669:
5660:
5656:
5647:
5640:
5636:
5621:
5617:
5608:
5604:
5599:
5596:
5595:
5570:
5553:
5539:
5537:
5534:
5533:
5511:
5508:
5507:
5486:
5469:
5461:
5457:
5435:
5422:
5418:
5410:
5407:
5406:
5405:We also define
5382:
5372:
5367:
5366:
5358:
5348:
5346:
5337:
5333:
5325:
5322:
5321:
5302:
5293:
5289:
5266:
5263:
5262:
5243:
5239:
5237:
5234:
5233:
5204:
5201:
5200:
5197:
5169:
5165:
5135:
5131:
5129:
5126:
5125:
5106:
5103:
5102:
5086:
5083:
5082:
5061:
5045:
5043:
5040:
5039:
5022:
5018:
5016:
5013:
5012:
4986:
4983:
4982:
4959:
4955:
4935:
4934:
4927:
4919:
4918:
4914:
4896:
4851:
4847:
4840:
4836:
4812:
4808:
4803:
4800:
4799:
4780:
4771:
4767:
4740:
4736:
4734:
4731:
4730:
4714:
4705:
4701:
4678:
4675:
4674:
4657:
4653:
4651:
4648:
4647:
4641:
4620:
4617:
4616:
4600:
4597:
4596:
4580:
4577:
4576:
4532:
4528:
4518:
4505:
4484:
4480:
4478:
4475:
4474:
4455:
4452:
4451:
4435:
4432:
4431:
4399:
4396:
4395:
4372:
4368:
4351:
4350:
4343:
4335:
4334:
4330:
4312:
4255:
4251:
4238:
4234:
4213:
4209:
4207:
4204:
4203:
4184:
4181:
4180:
4164:
4155:
4151:
4128:
4125:
4124:
4121:noise stability
4091:
4087:
4079:
4076:
4075:
4055:
4054:
4035:
4033:
4028:
4026:
4020:
4016:
4010:
4009:
3990:
3988:
3983:
3981:
3975:
3971:
3964:
3963:
3954:
3950:
3944:
3937:
3936:
3919:
3917:
3911:
3907:
3904:
3903:
3892:
3890:
3884:
3880:
3873:
3872:
3863:
3859:
3857:
3854:
3853:
3834:
3831:
3830:
3813:
3809:
3780:
3777:
3776:
3760:
3757:
3756:
3730:
3726:
3720:
3716:
3705:
3702:
3701:
3679:
3676:
3675:
3657:
3654:
3653:
3635:
3631:
3602:
3599:
3598:
3567:
3564:
3563:
3560:
3558:Noise stability
3532:
3527:
3519:
3479:
3474:
3444:
3442:
3439:
3438:
3400:
3396:
3373:
3370:
3369:
3346:
3342:
3325:
3324:
3311:
3303:
3302:
3298:
3293:
3285:
3279:
3254:
3250:
3240:
3235:
3208:
3204:
3202:
3199:
3198:
3172:
3168:
3151:
3150:
3137:
3129:
3128:
3124:
3112:
3090:
3086:
3074:
3070:
3042:
3037:
3031:
3028:
3027:
3008:
3005:
3004:
2952:
2949:
2948:
2921:
2918:
2917:
2901:
2898:
2897:
2881:
2878:
2877:
2846:
2842:
2825:
2824:
2819:
2811:
2805:
2780:
2776:
2770:
2759:
2735:
2732:
2731:
2712:
2709:
2708:
2705:total influence
2685:
2682:
2681:
2665:
2662:
2661:
2626:
2622:
2620:
2617:
2616:
2578:
2574:
2532:
2528:
2526:
2523:
2522:
2503:
2500:
2499:
2470:
2466:
2464:
2461:
2460:
2444:
2441:
2440:
2423:
2422:
2410:
2406:
2385:
2381:
2372:
2368:
2350:
2346:
2331:
2327:
2309:
2305:
2290:
2286:
2274:
2270:
2266:
2265:
2256:
2252:
2235:
2234:
2222:
2205:
2186:
2182:
2175:
2173:
2169:
2168:
2164:
2137:
2133:
2128:
2126:
2123:
2122:
2103:
2094:
2090:
2067:
2064:
2063:
2047:
2044:
2043:
2040:
2015:
2011:
1999:
1995:
1983:
1979:
1967:
1963:
1961:
1958:
1957:
1938:
1935:
1934:
1918:
1915:
1914:
1891:
1887:
1867:
1866:
1853:
1845:
1844:
1828:
1824:
1822:
1819:
1818:
1799:
1796:
1795:
1778:
1775:
1774:
1753:
1745:
1743:
1740:
1739:
1708:
1707:
1705:
1702:
1701:
1678:
1675:
1674:
1658:
1655:
1654:
1638:
1635:
1634:
1597:
1596:
1594:
1591:
1590:
1574:
1571:
1570:
1569:is the maximum
1554:
1545:
1541:
1518:
1515:
1514:
1507:
1482:
1478:
1461:
1460:
1448:
1424:
1421:
1420:
1401:
1398:
1397:
1375:
1372:
1371:
1348:
1344:
1327:
1326:
1320:
1304:
1300:
1282:
1278:
1270:
1267:
1266:
1246:
1242:
1225:
1222:
1221:
1164:
1163:
1161:
1158:
1157:
1131:
1127:
1095:
1094:
1092:
1089:
1088:
1039:
1035:
1013:
1000:
996:
976:
973:
972:
955:
951:
934:
931:
930:
909:
905:
903:
900:
899:
883:
880:
879:
840:
839:
837:
834:
833:
816:
811:
806:
803:
800:
799:
791:, which is the
776:
773:
772:
742:
738:
726:
704:
700:
681:
677:
657:
656:
638:
617:
614:
613:
594:
585:
581:
558:
555:
554:
551:
518:
515:
514:
483:
480:
479:
451:
447:
446:
442:
416:
412:
411:
407:
380:
376:
361:
357:
348:
344:
342:
339:
338:
318:
314:
300:
297:
296:
279:
275:
258:
255:
254:
238:
235:
234:
217:
213:
199:
196:
195:
178:
174:
157:
154:
153:
150:
96:
92:
75:
72:
71:
54:
50:
36:
33:
32:
17:
12:
11:
5:
13395:
13385:
13384:
13379:
13374:
13358:
13357:
13329:(1): 319–357,
13297:
13253:
13208:
13173:
13140:
13127:(3): 412–426.
13104:
13089:
13076:(3): 549–595.
13056:
13033:(1): 295–341.
13007:
12976:(1): 474–483.
12954:
12931:
12908:
12886:
12835:
12822:(3): 427–437.
12800:
12747:
12702:(3): 695–750.
12673:
12666:
12631:
12630:
12628:
12625:
12590:
12587:
12584:
12581:
12578:
12573:
12570:
12565:
12562:
12559:
12556:
12553:
12550:
12547:
12542:
12538:
12517:
12514:
12511:
12508:
12505:
12502:
12497:
12493:
12487:
12483:
12462:
12459:
12456:
12453:
12450:
12447:
12444:
12439:
12435:
12431:
12428:
12425:
12422:
12419:
12416:
12413:
12393:
12390:
12387:
12367:
12364:
12361:
12338:
12316:
12312:
12300:
12299:
12287:
12284:
12281:
12278:
12275:
12272:
12269:
12264:
12260:
12256:
12253:
12250:
12247:
12244:
12239:
12235:
12231:
12228:
12225:
12222:
12219:
12214:
12210:
12206:
12203:
12198:
12194:
12168:
12164:
12161:
12158:
12135:
12113:
12109:
12105:
12102:
12099:
12096:
12093:
12090:
12087:
12065:
12061:
12057:
12054:
12051:
12048:
12045:
12042:
12039:
12028:
12027:
12016:
12013:
12010:
12007:
12002:
11999:
11994:
11991:
11988:
11985:
11980:
11976:
11972:
11969:
11964:
11960:
11936:
11916:
11913:
11910:
11907:
11904:
11901:
11898:
11893:
11889:
11885:
11882:
11879:
11876:
11873:
11870:
11865:
11861:
11848:
11845:
11832:
11829:
11826:
11823:
11819:
11815:
11812:
11809:
11770:
11767:
11763:
11759:
11756:
11753:
11731:
11728:
11723:
11720:
11698:
11694:
11688:
11684:
11680:
11676:
11655:
11652:
11649:
11646:
11643:
11640:
11618:
11614:
11611:
11608:
11585:
11582:
11578:
11574:
11571:
11568:
11542:
11538:
11535:
11532:
11529:
11526:
11520:
11517:
11493:
11490:
11486:
11482:
11478:
11457:
11454:
11451:
11448:
11445:
11442:
11426:
11423:
11410:
11390:
11363:
11360:
11357:
11354:
11349:
11345:
11341:
11338:
11334:
11328:
11325:
11320:
11315:
11312:
11290:
11287:
11284:
11281:
11278:
11275:
11272:
11267:
11263:
11259:
11256:
11253:
11250:
11247:
11244:
11241:
11219:
11216:
11215:
11214:
11203:
11198:
11194:
11190:
11187:
11181:
11178:
11170:
11167:
11164:
11161:
11158:
11154:
11148:
11145:
11140:
11135:
11132:
11107:
11087:
11084:
11081:
11077:
11073:
11050:
11047:
11044:
11041:
11021:
11001:
10998:
10995:
10975:
10955:
10952:
10949:
10946:
10943:
10940:
10937:
10934:
10931:
10928:
10925:
10922:
10919:
10916:
10894:
10890:
10886:
10883:
10880:
10877:
10874:
10871:
10868:
10865:
10862:
10833:
10829:
10808:
10803:
10799:
10793:
10789:
10785:
10782:
10779:
10774:
10770:
10764:
10760:
10756:
10753:
10750:
10747:
10727:
10724:
10721:
10718:
10715:
10712:
10709:
10706:
10703:
10700:
10697:
10694:
10691:
10688:
10664:
10661:
10658:
10655:
10652:
10649:
10646:
10641:
10637:
10633:
10630:
10627:
10624:
10621:
10618:
10615:
10603:
10600:
10598:
10595:
10571:
10567:
10564:
10561:
10558:
10555:
10552:
10549:
10546:
10543:
10540:
10537:
10534:
10531:
10528:
10525:
10522:
10519:
10516:
10513:
10509:
10503:
10499:
10474:
10454:
10443:
10442:
10431:
10428:
10425:
10420:
10416:
10412:
10409:
10406:
10403:
10399:
10395:
10392:
10389:
10386:
10383:
10380:
10377:
10374:
10371:
10368:
10363:
10360:
10357:
10354:
10351:
10348:
10345:
10342:
10338:
10334:
10331:
10328:
10325:
10322:
10319:
10316:
10313:
10310:
10307:
10304:
10297:
10293:
10289:
10286:
10283:
10280:
10277:
10274:
10271:
10267:
10262:
10238:
10235:
10230:
10226:
10222:
10219:
10213:
10210:
10202:
10199:
10196:
10192:
10169:
10165:
10161:
10158:
10152:
10149:
10141:
10138:
10135:
10131:
10125:
10121:
10117:
10114:
10094:
10091:
10088:
10085:
10082:
10060:
10056:
10052:
10049:
10046:
10040:
10037:
10029:
10026:
10023:
10020:
10017:
10013:
10009:
10006:
9982:
9957:
9953:
9949:
9946:
9943:
9940:
9937:
9917:
9897:
9875:
9871:
9867:
9864:
9861:
9856:
9852:
9831:
9806:
9802:
9798:
9795:
9792:
9789:
9786:
9766:
9744:
9740:
9717:
9713:
9707:
9703:
9697:
9692:
9689:
9686:
9682:
9678:
9675:
9656:
9653:
9640:
9637:
9634:
9612:
9608:
9587:
9564:
9561:
9557:
9553:
9550:
9547:
9544:
9541:
9538:
9535:
9532:
9512:
9492:
9472:
9469:
9466:
9443:
9440:
9437:
9434:
9431:
9428:
9425:
9405:
9385:
9365:
9362:
9359:
9356:
9353:
9350:
9347:
9342:
9338:
9334:
9331:
9328:
9325:
9322:
9319:
9316:
9304:
9301:
9297:
9296:
9285:
9282:
9277:
9274:
9269:
9265:
9260:
9256:
9253:
9250:
9245:
9242:
9237:
9233:
9228:
9224:
9221:
9218:
9215:
9212:
9207:
9204:
9201:
9197:
9193:
9190:
9187:
9182:
9179:
9176:
9172:
9168:
9137:
9132:
9128:
9125:
9122:
9116:
9112:
9109:
9106:
9103:
9100:
9097:
9092:
9088:
9082:
9078:
9057:
9028:
9024:
9021:
9018:
9015:
9012:
9006:
9003:
9000:
8997:
8994:
8989:
8985:
8979:
8975:
8963:
8962:
8951:
8948:
8945:
8942:
8939:
8936:
8933:
8930:
8927:
8924:
8921:
8918:
8915:
8912:
8909:
8906:
8903:
8900:
8897:
8894:
8891:
8888:
8864:
8860:
8855:
8851:
8847:
8844:
8841:
8838:
8835:
8832:
8829:
8817:
8814:
8801:
8781:
8778:
8775:
8772:
8752:
8732:
8729:
8724:
8720:
8714:
8711:
8707:
8703:
8683:
8680:
8677:
8674:
8671:
8668:
8665:
8660:
8656:
8652:
8649:
8646:
8643:
8640:
8637:
8634:
8612:
8608:
8581:
8577:
8571:
8567:
8546:
8523:
8503:
8500:
8497:
8494:
8491:
8488:
8485:
8482:
8479:
8476:
8473:
8453:
8433:
8430:
8427:
8424:
8421:
8416:
8412:
8408:
8405:
8402:
8399:
8379:
8376:
8373:
8370:
8350:
8330:
8327:
8322:
8318:
8312:
8309:
8305:
8301:
8281:
8278:
8275:
8272:
8269:
8266:
8263:
8258:
8254:
8250:
8247:
8244:
8241:
8238:
8235:
8232:
8205:
8174:
8154:
8134:
8131:
8128:
8125:
8122:
8119:
8116:
8111:
8107:
8103:
8100:
8097:
8094:
8091:
8088:
8085:
8073:
8070:
8068:
8065:
8060:
8059:
8056:
8044:
8024:
8021:
8018:
7998:
7995:
7992:
7989:
7986:
7983:
7980:
7977:
7974:
7971:
7968:
7965:
7962:
7959:
7954:
7950:
7946:
7926:
7923:
7920:
7913:
7909:
7905:
7902:
7897:
7894:
7891:
7888:
7885:
7882:
7879:
7874:
7871:
7868:
7865:
7862:
7859:
7856:
7853:
7849:
7845:
7842:
7839:
7836:
7833:
7830:
7825:
7821:
7817:
7798:
7795:
7777:
7773:
7741:
7719:
7714:
7701:Gaussian space
7686:
7682:
7678:
7675:
7672:
7669:
7666:
7650:
7649:Gaussian space
7647:
7627:
7607:
7587:
7567:
7547:
7527:
7505:
7501:
7489:
7488:
7477:
7474:
7469:
7466:
7462:
7458:
7455:
7452:
7449:
7444:
7439:
7436:
7433:
7429:
7425:
7419:
7416:
7413:
7410:
7407:
7404:
7399:
7396:
7393:
7390:
7387:
7381:
7378:
7375:
7372:
7369:
7366:
7363:
7360:
7353:
7349:
7345:
7342:
7338:
7331:
7328:
7324:
7299:
7296:
7293:
7290:
7287:
7284:
7279:
7275:
7271:
7268:
7265:
7262:
7259:
7256:
7244:
7241:
7237:
7236:
7225:
7222:
7219:
7216:
7213:
7210:
7207:
7204:
7199:
7196:
7193:
7188:
7184:
7180:
7177:
7173:
7169:
7166:
7163:
7160:
7155:
7151:
7147:
7144:
7141:
7135:
7132:
7123:
7119:
7115:
7110:
7104:
7101:
7098:
7095:
7092:
7088:
7084:
7081:
7078:
7075:
7072:
7069:
7064:
7060:
7056:
7042:
7041:
7028:
7023:
7020:
7017:
7014:
7006:
7002:
6998:
6994:
6993:
6990:
6987:
6979:
6975:
6971:
6967:
6966:
6964:
6959:
6954:
6950:
6924:
6920:
6899:
6896:
6893:
6888:
6884:
6880:
6877:
6855:
6851:
6847:
6844:
6841:
6838:
6818:
6806:
6805:Noise operator
6803:
6802:
6801:
6790:
6785:
6781:
6777:
6774:
6768:
6765:
6758:
6754:
6750:
6744:
6740:
6736:
6733:
6730:
6727:
6724:
6719:
6715:
6709:
6704:
6701:
6698:
6694:
6690:
6687:
6684:
6681:
6678:
6675:
6661:
6660:
6649:
6646:
6641:
6637:
6631:
6628:
6624:
6620:
6617:
6614:
6611:
6608:
6605:
6602:
6599:
6596:
6593:
6590:
6587:
6584:
6579:
6575:
6571:
6568:
6562:
6559:
6551:
6548:
6545:
6541:
6537:
6534:
6531:
6528:
6525:
6520:
6516:
6492:
6480:
6477:
6469:
6468:
6457:
6452:
6448:
6444:
6441:
6438:
6432:
6429:
6421:
6418:
6415:
6412:
6409:
6405:
6401:
6398:
6371:
6351:
6336:
6335:
6324:
6318:
6314:
6311:
6308:
6303:
6299:
6295:
6292:
6289:
6286:
6283:
6279:
6273:
6266:
6262:
6259:
6256:
6249:
6245:
6237:
6233:
6230:
6227:
6222:
6218:
6214:
6211:
6208:
6205:
6202:
6198:
6192:
6185:
6182:
6179:
6175:
6169:
6164:
6161:
6158:
6155:
6150:
6146:
6119:
6116:
6113:
6093:
6082:
6081:
6070:
6065:
6060:
6056:
6052:
6049:
6046:
6041:
6037:
6032:
6028:
6025:
6022:
6019:
6012:
6008:
6002:
5998:
5993:
5989:
5986:
5983:
5980:
5975:
5971:
5945:
5941:
5916:
5913:
5910:
5907:
5904:
5882:
5878:
5874:
5871:
5868:
5865:
5845:
5825:
5822:
5800:
5796:
5792:
5789:
5786:
5783:
5780:
5768:
5762:
5745:
5742:
5739:
5717:
5716:
5705:
5699:
5696:
5691:
5687:
5684:
5681:
5676:
5672:
5668:
5663:
5659:
5655:
5643:
5639:
5635:
5632:
5629:
5624:
5620:
5616:
5611:
5607:
5603:
5580:
5577:
5573:
5569:
5566:
5563:
5560:
5556:
5552:
5549:
5545:
5542:
5521:
5518:
5515:
5493:
5489:
5485:
5482:
5479:
5476:
5472:
5464:
5460:
5456:
5453:
5450:
5447:
5444:
5441:
5438:
5434:
5430:
5425:
5421:
5417:
5414:
5403:
5402:
5391:
5385:
5380:
5375:
5370:
5365:
5361:
5357:
5354:
5351:
5345:
5340:
5336:
5332:
5329:
5317:is defined by
5305:
5301:
5296:
5292:
5288:
5285:
5282:
5279:
5276:
5273:
5270:
5261:of a function
5246:
5242:
5220:
5217:
5214:
5211:
5208:
5196:
5193:
5180:
5177:
5172:
5168:
5164:
5161:
5158:
5155:
5152:
5149:
5146:
5143:
5138:
5134:
5110:
5090:
5068:
5065:
5060:
5057:
5052:
5049:
5025:
5021:
4996:
4993:
4990:
4979:
4978:
4967:
4962:
4958:
4954:
4951:
4948:
4942:
4939:
4930:
4926:
4922:
4917:
4911:
4908:
4905:
4902:
4899:
4895:
4891:
4888:
4885:
4882:
4879:
4876:
4873:
4870:
4865:
4862:
4859:
4854:
4850:
4846:
4843:
4839:
4835:
4832:
4829:
4826:
4823:
4820:
4815:
4811:
4807:
4783:
4779:
4774:
4770:
4766:
4763:
4760:
4757:
4754:
4751:
4748:
4743:
4739:
4717:
4713:
4708:
4704:
4700:
4697:
4694:
4691:
4688:
4685:
4682:
4660:
4656:
4645:noise operator
4640:
4639:Noise operator
4637:
4624:
4604:
4584:
4573:
4572:
4561:
4558:
4555:
4552:
4549:
4544:
4541:
4538:
4535:
4531:
4525:
4522:
4517:
4512:
4509:
4504:
4501:
4498:
4495:
4492:
4487:
4483:
4459:
4439:
4415:
4412:
4409:
4406:
4403:
4392:
4391:
4380:
4375:
4371:
4367:
4364:
4358:
4355:
4346:
4342:
4338:
4333:
4327:
4324:
4321:
4318:
4315:
4311:
4307:
4304:
4301:
4298:
4295:
4292:
4289:
4286:
4283:
4280:
4277:
4274:
4269:
4266:
4263:
4258:
4254:
4250:
4247:
4244:
4241:
4237:
4233:
4230:
4227:
4224:
4221:
4216:
4212:
4188:
4167:
4163:
4158:
4154:
4150:
4147:
4144:
4141:
4138:
4135:
4132:
4123:of a function
4105:
4102:
4099:
4094:
4090:
4086:
4083:
4072:
4071:
4058:
4053:
4048:
4044:
4041:
4038:
4027:
4023:
4019:
4015:
4012:
4011:
4008:
4003:
3999:
3996:
3993:
3982:
3978:
3974:
3970:
3969:
3967:
3962:
3957:
3953:
3940:
3935:
3932:
3929:
3926:
3918:
3914:
3910:
3906:
3905:
3902:
3899:
3891:
3887:
3883:
3879:
3878:
3876:
3871:
3866:
3862:
3838:
3816:
3812:
3808:
3805:
3802:
3799:
3796:
3793:
3790:
3787:
3784:
3764:
3744:
3741:
3738:
3733:
3729:
3723:
3719:
3715:
3712:
3709:
3689:
3686:
3683:
3661:
3638:
3634:
3630:
3627:
3624:
3621:
3618:
3615:
3612:
3609:
3606:
3586:
3583:
3580:
3577:
3574:
3571:
3559:
3556:
3544:
3538:
3535:
3531:
3526:
3522:
3518:
3515:
3512:
3509:
3506:
3503:
3500:
3495:
3492:
3489:
3486:
3483:
3477:
3473:
3469:
3466:
3463:
3460:
3457:
3454:
3451:
3447:
3426:
3423:
3420:
3417:
3414:
3411:
3408:
3403:
3399:
3395:
3392:
3389:
3386:
3383:
3380:
3377:
3366:
3365:
3354:
3349:
3345:
3341:
3338:
3332:
3329:
3321:
3318:
3314:
3310:
3306:
3301:
3296:
3292:
3288:
3282:
3278:
3274:
3271:
3268:
3265:
3262:
3257:
3253:
3246:
3243:
3239:
3234:
3231:
3228:
3225:
3222:
3217:
3214:
3211:
3207:
3192:
3191:
3180:
3175:
3171:
3167:
3164:
3158:
3155:
3147:
3144:
3140:
3136:
3132:
3127:
3121:
3118:
3115:
3111:
3107:
3104:
3101:
3098:
3093:
3089:
3085:
3082:
3077:
3073:
3069:
3066:
3063:
3060:
3057:
3052:
3049:
3046:
3040:
3036:
3012:
2989:
2986:
2983:
2980:
2977:
2974:
2971:
2968:
2965:
2962:
2959:
2956:
2925:
2905:
2885:
2866:
2865:
2854:
2849:
2845:
2841:
2838:
2832:
2829:
2822:
2818:
2814:
2808:
2804:
2800:
2797:
2794:
2791:
2788:
2783:
2779:
2773:
2768:
2765:
2762:
2758:
2754:
2751:
2748:
2745:
2742:
2739:
2716:
2689:
2669:
2649:
2646:
2643:
2640:
2637:
2634:
2629:
2625:
2613:
2612:
2601:
2598:
2595:
2592:
2589:
2584:
2581:
2577:
2573:
2570:
2567:
2564:
2561:
2558:
2555:
2552:
2549:
2546:
2543:
2540:
2535:
2531:
2507:
2487:
2484:
2481:
2478:
2473:
2469:
2448:
2437:
2436:
2421:
2418:
2413:
2409:
2405:
2402:
2399:
2394:
2391:
2388:
2384:
2380:
2375:
2371:
2367:
2364:
2359:
2356:
2353:
2349:
2345:
2342:
2339:
2334:
2330:
2326:
2323:
2320:
2317:
2312:
2308:
2304:
2301:
2298:
2293:
2289:
2285:
2280:
2277:
2273:
2269:
2267:
2264:
2259:
2255:
2251:
2248:
2242:
2239:
2231:
2228:
2225:
2221:
2217:
2213:
2208:
2203:
2198:
2192:
2189:
2185:
2181:
2178:
2172:
2167:
2163:
2160:
2157:
2154:
2151:
2148:
2145:
2140:
2136:
2132:
2130:
2106:
2102:
2097:
2093:
2089:
2086:
2083:
2080:
2077:
2074:
2071:
2051:
2039:
2036:
2021:
2018:
2014:
2010:
2005:
2002:
1998:
1994:
1989:
1986:
1982:
1978:
1973:
1970:
1966:
1942:
1922:
1911:
1910:
1899:
1894:
1890:
1886:
1883:
1880:
1874:
1871:
1863:
1860:
1856:
1852:
1848:
1843:
1839:
1834:
1831:
1827:
1803:
1782:
1756:
1752:
1748:
1727:
1724:
1721:
1715:
1712:
1682:
1662:
1642:
1622:
1619:
1616:
1613:
1610:
1604:
1601:
1578:
1557:
1553:
1548:
1544:
1540:
1537:
1534:
1531:
1528:
1525:
1522:
1513:of a function
1506:
1503:
1502:
1501:
1490:
1485:
1481:
1477:
1474:
1468:
1465:
1457:
1454:
1451:
1447:
1443:
1440:
1437:
1434:
1431:
1428:
1405:
1385:
1382:
1379:
1368:
1367:
1356:
1351:
1347:
1343:
1340:
1334:
1331:
1323:
1319:
1315:
1312:
1307:
1303:
1299:
1296:
1293:
1290:
1285:
1281:
1277:
1274:
1249:
1245:
1241:
1238:
1235:
1232:
1229:
1214:expected value
1201:
1198:
1195:
1192:
1189:
1186:
1183:
1180:
1177:
1171:
1168:
1154:
1153:
1142:
1139:
1134:
1130:
1126:
1123:
1120:
1117:
1114:
1111:
1108:
1102:
1099:
1070:
1067:
1064:
1061:
1058:
1055:
1052:
1049:
1042:
1038:
1034:
1031:
1028:
1025:
1022:
1019:
1016:
1012:
1006:
1003:
999:
995:
992:
989:
986:
983:
980:
958:
954:
950:
947:
944:
941:
938:
912:
908:
887:
859:
856:
853:
847:
844:
819:
814:
809:
780:
762:
761:
750:
745:
741:
735:
732:
729:
725:
721:
718:
715:
712:
707:
703:
698:
695:
692:
689:
684:
680:
676:
673:
670:
664:
661:
653:
650:
647:
644:
641:
637:
633:
630:
627:
624:
621:
597:
593:
588:
584:
580:
577:
574:
571:
568:
565:
562:
550:
547:
534:
531:
528:
525:
522:
502:
499:
496:
493:
490:
487:
476:
475:
464:
461:
454:
450:
445:
441:
438:
435:
432:
429:
426:
419:
415:
410:
406:
403:
400:
397:
394:
391:
388:
383:
379:
375:
372:
369:
364:
360:
356:
351:
347:
321:
317:
313:
310:
307:
304:
282:
278:
274:
271:
268:
265:
262:
253:is defined on
242:
220:
216:
212:
209:
206:
203:
181:
177:
173:
170:
167:
164:
161:
149:
148:Basic concepts
146:
99:
95:
91:
88:
85:
82:
79:
57:
53:
49:
46:
43:
40:
15:
9:
6:
4:
3:
2:
13394:
13383:
13380:
13378:
13375:
13373:
13370:
13369:
13367:
13354:
13350:
13346:
13342:
13337:
13332:
13328:
13324:
13323:
13315:
13311:
13307:
13306:Khot, Subhash
13301:
13293:
13289:
13284:
13279:
13275:
13271:
13268:(June 2023).
13267:
13263:
13257:
13250:
13246:
13241:
13236:
13232:
13228:
13227:
13219:
13212:
13203:
13198:
13194:
13190:
13189:
13184:
13177:
13168:
13163:
13159:
13155:
13151:
13144:
13135:
13130:
13126:
13122:
13115:
13108:
13100:
13093:
13084:
13079:
13075:
13071:
13067:
13060:
13051:
13046:
13041:
13036:
13032:
13028:
13027:
13022:
13018:
13011:
13003:
12999:
12994:
12989:
12984:
12983:10.1.1.7.5597
12979:
12975:
12971:
12970:
12969:Combinatorica
12965:
12958:
12950:
12946:
12942:
12935:
12927:
12923:
12919:
12912:
12904:
12897:
12890:
12882:
12876:
12868:
12864:
12859:
12854:
12850:
12846:
12839:
12830:
12825:
12821:
12817:
12816:
12811:
12804:
12796:
12792:
12787:
12782:
12777:
12772:
12768:
12764:
12763:
12758:
12751:
12743:
12739:
12735:
12731:
12727:
12723:
12719:
12715:
12710:
12705:
12701:
12697:
12696:
12691:
12687:
12683:
12677:
12669:
12663:
12658:
12653:
12649:
12645:
12639:
12637:
12632:
12624:
12622:
12618:
12614:
12609:
12607:
12602:
12588:
12585:
12582:
12579:
12576:
12571:
12568:
12563:
12560:
12557:
12551:
12545:
12540:
12536:
12515:
12512:
12506:
12500:
12495:
12491:
12485:
12457:
12454:
12451:
12448:
12437:
12429:
12426:
12423:
12420:
12414:
12411:
12404:such that if
12391:
12388:
12385:
12378:there exists
12365:
12362:
12359:
12350:
12336:
12314:
12310:
12285:
12282:
12273:
12267:
12262:
12258:
12254:
12248:
12242:
12237:
12233:
12223:
12220:
12212:
12208:
12201:
12196:
12192:
12184:
12183:
12182:
12166:
12162:
12159:
12156:
12133:
12111:
12103:
12100:
12097:
12094:
12088:
12085:
12063:
12055:
12052:
12049:
12046:
12040:
12037:
12014:
12011:
12008:
12005:
12000:
11997:
11992:
11989:
11978:
11974:
11967:
11962:
11958:
11950:
11949:
11948:
11934:
11911:
11908:
11905:
11902:
11891:
11883:
11880:
11877:
11874:
11868:
11863:
11859:
11844:
11827:
11824:
11821:
11817:
11813:
11807:
11799:
11794:
11792:
11786:
11784:
11765:
11761:
11757:
11729:
11726:
11721:
11718:
11696:
11692:
11686:
11682:
11678:
11674:
11650:
11647:
11644:
11638:
11616:
11612:
11609:
11606:
11580:
11576:
11572:
11566:
11558:
11540:
11536:
11533:
11530:
11527:
11524:
11518:
11515:
11491:
11488:
11484:
11480:
11476:
11452:
11449:
11446:
11440:
11432:
11431:random graphs
11422:
11408:
11388:
11380:
11375:
11358:
11352:
11347:
11343:
11339:
11336:
11332:
11326:
11323:
11318:
11313:
11310:
11285:
11282:
11279:
11276:
11265:
11257:
11254:
11251:
11248:
11242:
11239:
11230:
11228:
11224:
11201:
11196:
11188:
11176:
11165:
11159:
11156:
11152:
11146:
11143:
11138:
11133:
11130:
11121:
11120:
11119:
11105:
11085:
11082:
11079:
11075:
11071:
11062:
11045:
11039:
11019:
10999:
10996:
10993:
10973:
10950:
10944:
10938:
10932:
10929:
10923:
10920:
10914:
10892:
10884:
10881:
10878:
10875:
10869:
10866:
10863:
10860:
10852:
10847:
10831:
10827:
10801:
10797:
10791:
10787:
10783:
10780:
10777:
10772:
10768:
10762:
10758:
10751:
10748:
10745:
10722:
10716:
10710:
10704:
10701:
10695:
10692:
10686:
10678:
10659:
10656:
10653:
10650:
10639:
10631:
10628:
10625:
10622:
10616:
10613:
10594:
10592:
10590:
10584:
10562:
10559:
10553:
10547:
10538:
10532:
10529:
10523:
10517:
10501:
10488:
10472:
10452:
10429:
10423:
10418:
10414:
10410:
10404:
10401:
10397:
10384:
10378:
10372:
10366:
10358:
10355:
10352:
10346:
10343:
10340:
10332:
10320:
10314:
10308:
10302:
10295:
10287:
10284:
10281:
10278:
10272:
10269:
10260:
10252:
10251:
10250:
10236:
10233:
10228:
10220:
10208:
10197:
10194:
10190:
10167:
10159:
10147:
10139:
10136:
10133:
10129:
10123:
10115:
10112:
10092:
10089:
10086:
10083:
10080:
10058:
10054:
10047:
10035:
10024:
10018:
10015:
10011:
10007:
10004:
9996:
9980:
9971:
9955:
9947:
9944:
9941:
9938:
9915:
9895:
9873:
9869:
9865:
9862:
9859:
9854:
9850:
9829:
9820:
9804:
9796:
9793:
9790:
9787:
9764:
9742:
9738:
9715:
9711:
9705:
9701:
9695:
9690:
9687:
9684:
9680:
9676:
9673:
9664:
9662:
9652:
9638:
9635:
9632:
9610:
9606:
9585:
9576:
9575:coordinates.
9559:
9555:
9548:
9542:
9539:
9533:
9530:
9510:
9490:
9470:
9467:
9464:
9455:
9441:
9438:
9432:
9426:
9423:
9403:
9383:
9360:
9357:
9354:
9351:
9340:
9332:
9329:
9326:
9323:
9317:
9314:
9300:
9283:
9275:
9272:
9267:
9263:
9258:
9254:
9251:
9248:
9243:
9240:
9235:
9231:
9226:
9219:
9216:
9213:
9205:
9202:
9199:
9195:
9191:
9188:
9185:
9180:
9177:
9174:
9170:
9159:
9158:
9157:
9155:
9150:
9135:
9130:
9126:
9123:
9120:
9114:
9107:
9101:
9095:
9090:
9086:
9080:
9055:
9047:
9042:
9026:
9019:
9013:
9010:
9004:
8998:
8992:
8987:
8983:
8977:
8949:
8943:
8937:
8934:
8931:
8928:
8925:
8922:
8919:
8913:
8907:
8904:
8901:
8895:
8889:
8886:
8879:
8878:
8877:
8853:
8845:
8842:
8839:
8836:
8830:
8827:
8813:
8799:
8776:
8770:
8750:
8730:
8727:
8722:
8712:
8709:
8705:
8678:
8675:
8672:
8669:
8658:
8650:
8647:
8644:
8641:
8635:
8632:
8610:
8606:
8597:
8579:
8575:
8569:
8565:
8544:
8535:
8521:
8498:
8492:
8489:
8483:
8480:
8477:
8451:
8428:
8422:
8419:
8414:
8406:
8403:
8400:
8374:
8368:
8348:
8328:
8325:
8320:
8310:
8307:
8303:
8276:
8273:
8270:
8267:
8256:
8248:
8245:
8242:
8239:
8233:
8230:
8222:
8218:
8203:
8195:
8190:
8188:
8172:
8152:
8129:
8126:
8123:
8120:
8109:
8101:
8098:
8095:
8092:
8086:
8083:
8067:Basic results
8064:
8057:
8042:
8035:is a pair of
8022:
8019:
8016:
7990:
7984:
7978:
7972:
7966:
7957:
7952:
7948:
7918:
7911:
7907:
7903:
7900:
7895:
7892:
7889:
7883:
7877:
7869:
7866:
7863:
7857:
7854:
7851:
7843:
7837:
7828:
7823:
7819:
7807:
7803:
7799:
7796:
7793:
7775:
7771:
7762:
7761:
7760:
7757:
7755:
7752:-dimensional
7739:
7717:
7702:
7684:
7676:
7673:
7670:
7667:
7656:
7646:
7644:
7639:
7625:
7605:
7585:
7565:
7545:
7525:
7503:
7499:
7475:
7467:
7464:
7460:
7456:
7453:
7442:
7437:
7434:
7431:
7427:
7423:
7414:
7411:
7408:
7402:
7394:
7388:
7385:
7379:
7370:
7364:
7358:
7351:
7347:
7343:
7340:
7329:
7326:
7322:
7313:
7312:
7311:
7294:
7291:
7288:
7277:
7269:
7266:
7263:
7257:
7254:
7240:
7223:
7214:
7208:
7202:
7194:
7186:
7182:
7178:
7175:
7167:
7161:
7153:
7149:
7142:
7130:
7117:
7108:
7099:
7093:
7090:
7086:
7082:
7076:
7067:
7062:
7058:
7047:
7046:
7045:
7021:
7018:
7015:
7012:
7000:
6996:
6988:
6985:
6973:
6969:
6962:
6957:
6952:
6948:
6940:
6939:
6938:
6922:
6918:
6894:
6886:
6882:
6878:
6875:
6853:
6849:
6845:
6842:
6839:
6836:
6816:
6788:
6783:
6775:
6763:
6752:
6742:
6738:
6734:
6728:
6722:
6717:
6713:
6707:
6702:
6699:
6696:
6692:
6688:
6682:
6676:
6673:
6666:
6665:
6664:
6647:
6639:
6629:
6626:
6622:
6618:
6615:
6606:
6597:
6594:
6591:
6585:
6582:
6577:
6569:
6557:
6549:
6546:
6543:
6539:
6535:
6529:
6523:
6518:
6514:
6506:
6505:
6504:
6490:
6476:
6474:
6455:
6450:
6446:
6439:
6427:
6416:
6410:
6407:
6403:
6399:
6396:
6389:
6388:
6387:
6385:
6369:
6349:
6341:
6322:
6309:
6306:
6301:
6297:
6293:
6290:
6287:
6284:
6271:
6264:
6260:
6257:
6254:
6247:
6243:
6228:
6225:
6220:
6216:
6212:
6209:
6206:
6203:
6190:
6183:
6180:
6177:
6173:
6167:
6162:
6156:
6148:
6144:
6136:
6135:
6134:
6131:
6117:
6114:
6111:
6091:
6068:
6058:
6054:
6050:
6047:
6039:
6035:
6026:
6023:
6020:
6010:
6006:
6000:
5996:
5991:
5987:
5981:
5973:
5969:
5961:
5960:
5959:
5943:
5939:
5930:
5914:
5911:
5908:
5905:
5902:
5880:
5872:
5869:
5866:
5843:
5823:
5820:
5798:
5790:
5787:
5784:
5781:
5766:
5761:
5759:
5743:
5740:
5737:
5728:
5726:
5722:
5703:
5697:
5694:
5685:
5679:
5674:
5666:
5661:
5657:
5641:
5633:
5627:
5622:
5614:
5609:
5605:
5594:
5593:
5592:
5575:
5571:
5567:
5564:
5561:
5554:
5550:
5547:
5543:
5540:
5519:
5516:
5513:
5504:
5491:
5480:
5474:
5462:
5454:
5451:
5448:
5445:
5439:
5436:
5428:
5415:
5389:
5383:
5373:
5363:
5352:
5343:
5338:
5330:
5320:
5319:
5318:
5294:
5286:
5283:
5280:
5277:
5271:
5268:
5260:
5244:
5240:
5215:
5212:
5209:
5206:
5192:
5175:
5170:
5166:
5162:
5159:
5153:
5147:
5141:
5136:
5132:
5122:
5108:
5088:
5066:
5063:
5058:
5055:
5050:
5047:
5023:
5019:
5010:
4994:
4991:
4988:
4965:
4960:
4956:
4949:
4937:
4924:
4915:
4906:
4900:
4897:
4893:
4889:
4880:
4874:
4868:
4860:
4852:
4848:
4844:
4841:
4833:
4827:
4818:
4813:
4809:
4798:
4797:
4796:
4772:
4764:
4761:
4758:
4755:
4749:
4746:
4741:
4737:
4706:
4698:
4695:
4692:
4689:
4683:
4680:
4658:
4654:
4646:
4636:
4622:
4602:
4582:
4559:
4553:
4547:
4542:
4539:
4536:
4533:
4529:
4523:
4520:
4515:
4510:
4507:
4502:
4496:
4490:
4485:
4481:
4473:
4472:
4471:
4457:
4437:
4429:
4413:
4410:
4407:
4404:
4401:
4378:
4373:
4365:
4353:
4340:
4331:
4322:
4316:
4313:
4309:
4305:
4296:
4290:
4284:
4278:
4272:
4264:
4256:
4252:
4248:
4245:
4242:
4239:
4231:
4225:
4219:
4214:
4210:
4202:
4201:
4200:
4186:
4156:
4148:
4145:
4142:
4139:
4133:
4130:
4122:
4117:
4100:
4092:
4088:
4084:
4081:
4051:
4046:
4042:
4039:
4036:
4021:
4017:
4013:
4006:
4001:
3997:
3994:
3991:
3976:
3972:
3965:
3960:
3955:
3951:
3933:
3930:
3927:
3924:
3912:
3908:
3900:
3897:
3885:
3881:
3874:
3869:
3864:
3860:
3852:
3851:
3850:
3836:
3814:
3806:
3803:
3800:
3797:
3791:
3788:
3785:
3782:
3762:
3742:
3739:
3731:
3727:
3721:
3717:
3710:
3687:
3684:
3681:
3673:
3659:
3636:
3628:
3625:
3622:
3619:
3613:
3610:
3607:
3604:
3584:
3581:
3578:
3575:
3572:
3569:
3555:
3542:
3536:
3533:
3529:
3524:
3513:
3510:
3504:
3498:
3490:
3487:
3484:
3475:
3471:
3467:
3461:
3455:
3452:
3421:
3418:
3415:
3412:
3401:
3393:
3390:
3387:
3384:
3378:
3375:
3352:
3347:
3339:
3327:
3319:
3316:
3308:
3299:
3290:
3280:
3276:
3272:
3266:
3260:
3255:
3251:
3244:
3241:
3237:
3232:
3226:
3220:
3212:
3197:
3196:
3195:
3178:
3173:
3165:
3153:
3145:
3142:
3134:
3125:
3119:
3116:
3113:
3109:
3105:
3099:
3096:
3091:
3080:
3075:
3071:
3067:
3061:
3055:
3047:
3038:
3034:
3026:
3025:
3024:
3010:
3001:
2984:
2981:
2978:
2975:
2969:
2963:
2957:
2954:
2946:
2945:Hamming graph
2942:
2937:
2923:
2903:
2883:
2875:
2871:
2852:
2847:
2839:
2827:
2816:
2806:
2802:
2798:
2792:
2786:
2781:
2777:
2771:
2766:
2763:
2760:
2756:
2752:
2746:
2740:
2737:
2730:
2729:
2728:
2714:
2706:
2701:
2687:
2667:
2647:
2644:
2638:
2632:
2627:
2623:
2599:
2590:
2582:
2579:
2575:
2571:
2565:
2559:
2550:
2544:
2538:
2533:
2529:
2521:
2520:
2519:
2505:
2482:
2476:
2471:
2467:
2446:
2419:
2411:
2407:
2403:
2400:
2397:
2392:
2389:
2386:
2382:
2378:
2373:
2369:
2365:
2362:
2357:
2354:
2351:
2347:
2343:
2340:
2337:
2332:
2328:
2321:
2318:
2310:
2306:
2302:
2299:
2296:
2291:
2287:
2278:
2275:
2271:
2262:
2257:
2249:
2237:
2229:
2226:
2223:
2219:
2215:
2211:
2206:
2201:
2196:
2190:
2187:
2183:
2179:
2176:
2170:
2165:
2161:
2155:
2149:
2143:
2138:
2134:
2121:
2120:
2119:
2095:
2087:
2084:
2081:
2078:
2072:
2069:
2049:
2035:
2019:
2016:
2012:
2008:
2003:
2000:
1996:
1992:
1987:
1984:
1980:
1976:
1971:
1968:
1964:
1954:
1940:
1920:
1897:
1892:
1888:
1881:
1869:
1861:
1858:
1850:
1841:
1837:
1832:
1829:
1825:
1817:
1816:
1815:
1801:
1793:
1780:
1769:
1750:
1722:
1710:
1699:
1694:
1680:
1660:
1640:
1633:for some set
1620:
1617:
1611:
1599:
1576:
1546:
1538:
1535:
1532:
1529:
1523:
1520:
1512:
1488:
1483:
1475:
1463:
1452:
1449:
1445:
1441:
1435:
1429:
1426:
1419:
1418:
1417:
1403:
1380:
1377:
1354:
1349:
1341:
1329:
1321:
1317:
1313:
1305:
1301:
1294:
1288:
1283:
1275:
1265:
1264:
1263:
1247:
1239:
1236:
1233:
1230:
1219:
1215:
1196:
1190:
1184:
1166:
1140:
1132:
1128:
1124:
1121:
1115:
1109:
1097:
1087:
1086:
1085:
1082:
1065:
1059:
1053:
1047:
1040:
1032:
1029:
1026:
1023:
1017:
1014:
1010:
1004:
1001:
997:
993:
987:
984:
981:
956:
948:
945:
942:
939:
928:
925:are known as
910:
906:
885:
877:
873:
870:are known as
854:
842:
817:
812:
798:
794:
778:
770:
765:
748:
743:
739:
733:
730:
727:
723:
719:
713:
705:
701:
696:
690:
682:
678:
671:
659:
648:
642:
639:
635:
631:
625:
619:
612:
611:
610:
586:
578:
575:
572:
569:
563:
560:
546:
529:
526:
523:
497:
494:
491:
488:
462:
452:
448:
439:
436:
430:
427:
424:
417:
413:
404:
401:
392:
389:
381:
377:
373:
370:
367:
362:
358:
349:
345:
337:
336:
335:
319:
311:
308:
305:
280:
272:
269:
266:
263:
240:
218:
210:
207:
204:
179:
171:
168:
165:
162:
145:
143:
139:
135:
131:
130:random graphs
127:
123:
122:combinatorics
119:
115:
97:
89:
86:
83:
80:
55:
47:
44:
41:
30:
26:
22:
13326:
13320:
13300:
13273:
13262:Eldan, Ronen
13256:
13230:
13224:
13211:
13192:
13186:
13176:
13157:
13153:
13143:
13124:
13120:
13107:
13098:
13092:
13073:
13069:
13059:
13040:math/0503503
13030:
13024:
13010:
12973:
12967:
12957:
12940:
12934:
12917:
12911:
12902:
12896:"Chapter 16"
12889:
12875:cite journal
12848:
12838:
12819:
12813:
12803:
12766:
12760:
12750:
12699:
12693:
12676:
12647:
12610:
12603:
12351:
12301:
12029:
11850:
11795:
11787:
11782:
11556:
11428:
11376:
11231:
11221:
11063:
10848:
10676:
10605:
10588:
10585:
10487:CDF distance
10444:
9972:
9821:
9665:
9658:
9577:
9456:
9306:
9298:
9153:
9151:
9045:
9043:
8964:
8819:
8595:
8536:
8220:
8216:
8193:
8191:
8187:dictatorship
8186:
8075:
8061:
7808:), given by
7758:
7700:
7652:
7640:
7490:
7246:
7238:
7043:
6937:is given by
6808:
6662:
6482:
6472:
6470:
6383:
6339:
6337:
6132:
6083:
5958:is given by
5928:
5770:
5764:
5757:
5756:is known as
5729:
5718:
5505:
5404:
5198:
5123:
4980:
4644:
4642:
4574:
4427:
4393:
4120:
4118:
4073:
3652:
3561:
3367:
3193:
3002:
2938:
2873:
2869:
2867:
2704:
2702:
2614:
2438:
2041:
1955:
1912:
1772:
1770:
1738:is on level
1697:
1695:
1510:
1508:
1369:
1212:, where the
1155:
1083:
926:
875:
871:
767:This is the
766:
763:
552:
477:
233:instead. If
151:
142:PAC learning
28:
18:
13233:(4): 1–50,
12682:P. Diaconis
11798:KKL theorem
11791:percolation
11379:FKN theorem
9046:KKL theorem
8194:FKN theorem
3672:-correlated
2874:sensitivity
1370:If we skip
21:mathematics
13366:Categories
13283:2208.06508
13101:. FOCS'95.
12858:2005.00566
12734:0867.60043
12657:2105.10386
12627:References
10105:, and let
8694:satisfies
7643:Friedgut's
7598:occurs at
7009:w.p.
6982:w.p.
6809:A pair of
4030:w.p.
3985:w.p.
3921:w.p.
3894:w.p.
1589:such that
13331:CiteSeerX
13235:CiteSeerX
12978:CiteSeerX
12776:1108.1210
12742:Q62111462
12718:1050-5164
12589:ε
12583:ρ
12580:
12572:π
12564:−
12558:≤
12546:
12541:ρ
12516:τ
12513:≤
12501:
12449:−
12443:→
12421:−
12415::
12386:τ
12360:ε
12337:ρ
12283:−
12268:
12243:
12202:
12197:ρ
12163:ρ
12160:−
12095:−
12089:∈
12047:−
12041:∈
12012:ρ
12009:
12001:π
11993:−
11987:⟶
11968:
11963:ρ
11903:−
11897:→
11875:−
11869::
11825:
11752:Θ
11722:∼
11679:−
11610:
11528:
11519:∼
11489:−
11481:−
11353:
11337:−
11319:−
11277:−
11271:→
11249:−
11243::
11180:^
11160:⊆
11153:∑
11086:ε
11046:ε
11000:ε
10997:−
10876:−
10870:∈
10828:χ
10781:…
10651:−
10645:→
10623:−
10617::
10539:−
10453:ψ
10424:ε
10373:ψ
10367:
10344:∼
10333:−
10309:ψ
10303:
10279:−
10273:∼
10234:≤
10212:^
10201:∅
10198:≠
10191:∑
10151:^
10137:∋
10130:∑
10113:ε
10090:
10055:χ
10039:^
10019:⊆
10012:∑
9981:ψ
9939:−
9863:…
9788:−
9681:∑
9636:≈
9625:for some
9607:μ
9560:ε
9543:
9534:
9511:ε
9465:ε
9439:≤
9427:
9352:−
9346:→
9324:−
9318::
9255:∧
9252:⋯
9249:∧
9220:∨
9217:⋯
9214:∨
9192:∧
9189:⋯
9186:∧
9124:
9111:Ω
9096:
9014:
9005:≥
8993:
8938:
8932:⋅
8926:
8920:≤
8908:
8902:≤
8890:
8859:→
8837:−
8831::
8777:ε
8731:ε
8719:‖
8702:‖
8670:−
8664:→
8642:−
8636::
8499:ε
8481:≠
8429:ε
8411:‖
8404:−
8398:‖
8375:ε
8329:ε
8317:‖
8300:‖
8268:−
8262:→
8240:−
8234::
8121:−
8115:→
8093:−
8087::
8043:ρ
7979:
7953:ρ
7908:ρ
7904:−
7890:ρ
7878:
7855:∼
7824:ρ
7668:−
7500:μ
7465:⊕
7457:≠
7428:∑
7412:−
7389:
7359:
7348:μ
7344:∼
7283:→
7258::
7203:
7187:ρ
7179:∼
7150:ω
7134:^
7109:ρ
7094:⊆
7087:∑
7063:ρ
7019:ρ
7016:−
6986:ρ
6923:ρ
6887:ρ
6879:∼
6850:μ
6846:∼
6817:ρ
6767:^
6739:∑
6723:
6693:∑
6677:
6627:⊕
6619:−
6607:
6595:−
6561:^
6547:∋
6540:∑
6524:
6479:Influence
6447:ω
6431:^
6411:⊆
6404:∑
6288:∈
6258:−
6248:−
6207:∈
6181:−
6145:ω
6115:−
6051:−
6036:∑
6024:−
5997:∑
5970:μ
5940:μ
5821:−
5782:−
5690:‖
5683:‖
5680:≤
5671:‖
5662:ρ
5654:‖
5638:‖
5631:‖
5628:≤
5619:‖
5610:ρ
5602:‖
5565:−
5446:−
5440:∈
5424:∞
5420:‖
5413:‖
5353:
5335:‖
5328:‖
5300:→
5278:−
5272::
5219:∞
5210:≤
5179:⟩
5171:ρ
5157:⟨
5142:
5137:ρ
5067:ρ
5059:
5024:ρ
4989:ρ
4957:χ
4941:^
4916:ρ
4901:⊆
4894:∑
4869:
4853:ρ
4845:∼
4814:ρ
4795:given by
4778:→
4756:−
4750::
4742:ρ
4712:→
4690:−
4684::
4659:ρ
4623:δ
4548:
4543:δ
4537:−
4516:−
4491:
4486:δ
4458:δ
4411:≤
4408:δ
4405:≤
4357:^
4332:ρ
4317:⊆
4310:∑
4273:
4257:ρ
4249:∼
4220:
4215:ρ
4187:ρ
4162:→
4140:−
4134::
4093:ρ
4085:∼
4043:ρ
4040:−
4014:−
3998:ρ
3931:ρ
3928:−
3898:ρ
3798:−
3792:∈
3763:ρ
3743:ρ
3711:
3660:ρ
3620:−
3614:∈
3582:≤
3579:ρ
3576:≤
3570:−
3537:ϵ
3534:δ
3525:≤
3514:ϵ
3511:≥
3499:
3491:δ
3488:−
3456:∈
3413:−
3407:→
3385:−
3331:^
3317:−
3300:ρ
3277:∑
3261:
3256:ρ
3245:ρ
3221:
3213:ρ
3157:^
3143:−
3126:ρ
3117:∋
3110:∑
3097:
3081:
3076:ρ
3056:
3048:ρ
3011:ρ
2988:⟩
2973:⟨
2958:
2831:^
2803:∑
2787:
2757:∑
2741:
2633:
2580:⊕
2572:≠
2539:
2477:
2401:…
2366:−
2355:−
2341:…
2300:…
2276:⊕
2241:^
2227:∋
2220:∑
2188:⊕
2180:−
2162:
2144:
2101:→
2079:−
2073::
2038:Influence
2017:≤
2001:≥
1889:χ
1873:^
1842:∑
1714:^
1618:≠
1603:^
1552:→
1530:−
1524::
1467:^
1456:∅
1453:≠
1446:∑
1430:
1384:∅
1333:^
1318:∑
1295:
1280:‖
1273:‖
1231:−
1191:
1179:∅
1170:^
1138:⟩
1129:χ
1119:⟨
1101:^
1024:−
1018:∈
1011:∑
1002:−
991:⟩
979:⟨
940:−
907:χ
846:^
731:∈
724:∏
702:χ
679:χ
663:^
643:⊆
636:∑
592:→
570:−
564::
489:−
437:−
428:…
402:−
371:…
264:−
163:−
81:−
13312:(2007),
13002:15534278
12795:15933352
12738:Wikidata
12646:(2014).
10738:, where
8009:, where
6910:, where
5698:′
5544:′
1794:part of
1653:of size
13353:2090495
12726:1410112
12617:MAX-CUT
12528:, then
11098:, then
10591:theorem
10249:. Then
9730:and no
8341:, then
2943:of the
1773:degree
795:in the
13351:
13333:
13237:
13000:
12980:
12793:
12740:
12732:
12724:
12716:
12664:
12577:arccos
12006:arccos
10677:linear
10073:, let
9997:, let
9376:is an
9154:Tribes
8217:almost
5927:, the
5895:. For
5231:, the
4426:, the
3562:Given
1698:levels
1511:degree
140:, and
13349:S2CID
13317:(PDF)
13278:arXiv
13221:(PDF)
13117:(PDF)
13035:arXiv
12998:S2CID
12899:(PDF)
12853:arXiv
12791:S2CID
12771:arXiv
12652:arXiv
11711:when
11012:then
10966:. If
9777:over
8743:then
8596:junta
8221:close
8185:is a
5259:-norm
4981:When
2660:then
1220:over
797:group
12881:link
12714:ISSN
12662:ISBN
12615:for
12537:Stab
12389:>
12363:>
12193:Stab
11959:Stab
11851:Let
11377:The
11333:Stab
10560:<
10530:<
9468:>
8728:<
8710:>
8326:<
8308:>
8292:and
6483:The
6338:The
5912:<
5906:<
5741:<
5532:and
5517:>
5216:<
5199:For
5133:Stab
4992:>
4643:The
4530:Stab
4394:For
4211:Stab
4119:The
3651:are
3252:Stab
3072:Stab
2703:The
2042:The
1985:<
1969:>
1771:The
1509:The
23:and
13341:doi
13288:doi
13245:doi
13197:doi
13193:124
13162:doi
13129:doi
13078:doi
13045:doi
13031:171
12988:doi
12945:doi
12922:doi
12863:doi
12824:doi
12781:doi
12730:Zbl
12704:doi
12492:Inf
12482:max
12259:Maj
12234:Maj
12209:Maj
11975:Maj
11860:Maj
11822:log
11607:log
11525:log
11508:if
11032:is
10849:In
10675:is
10498:sup
10120:max
10087:deg
9540:Inf
9531:exp
9503:is
9424:Inf
9307:If
9121:log
9087:Inf
9077:max
9011:Var
8984:Inf
8974:max
8935:Var
8923:deg
8905:Inf
8887:Var
8763:is
8361:is
8076:If
7386:Inf
6714:Inf
6674:Inf
6515:Inf
5836:or
5723:of
5649:and
5433:max
5056:log
4575:If
4470:is
4450:at
4430:of
4179:at
3472:Inf
3035:Inf
2955:Inf
2778:Inf
2738:Inf
2707:of
2624:Inf
2615:If
2530:Inf
2468:Inf
2439:If
2135:Inf
1814:is
1427:Var
878:of
334:is
70:or
19:In
13368::
13347:,
13339:,
13327:37
13325:,
13319:,
13286:.
13272:.
13243:,
13231:12
13229:,
13223:,
13191:.
13185:.
13158:12
13156:.
13152:.
13125:29
13123:.
13119:.
13074:47
13072:.
13068:.
13043:.
13029:.
13023:.
12996:.
12986:.
12974:18
12972:.
12966:.
12901:.
12877:}}
12873:{{
12861:.
12851:.
12847:.
12820:29
12818:.
12812:.
12789:.
12779:.
12767:23
12765:.
12759:.
12736:.
12728:.
12722:MR
12720:.
12712:.
12698:.
12692:.
12684:;
12660:.
12635:^
12601:.
12349:.
12227:Pr
11843:.
11793:.
11785:.
10846:.
10593:.
10583:.
10542:Pr
10512:Pr
9651:.
9149:.
9041:.
8876:,
8812:.
8534:.
8472:Pr
7756:.
7645:.
7638:.
7448:Pr
7310:,
6130:.
5760:.
5727:.
5591:,
5191:.
4482:NS
4116:.
3946:or
3000:.
2554:Pr
2034:.
1953:.
1768:.
1416::
1081:.
350:01
144:.
136:,
128:,
124:,
27:,
13343::
13294:.
13290::
13280::
13247::
13205:.
13199::
13170:.
13164::
13137:.
13131::
13086:.
13080::
13053:.
13047::
13037::
13004:.
12990::
12951:.
12947::
12928:.
12924::
12883:)
12865::
12855::
12832:.
12826::
12797:.
12783::
12773::
12744:.
12706::
12700:6
12670:.
12654::
12586:+
12569:2
12561:1
12555:]
12552:f
12549:[
12510:]
12507:f
12504:[
12496:i
12486:i
12461:}
12458:1
12455:,
12452:1
12446:{
12438:n
12434:}
12430:1
12427:,
12424:1
12418:{
12412:f
12392:0
12366:0
12315:i
12311:x
12298:.
12286:1
12280:]
12277:)
12274:y
12271:(
12263:n
12255:=
12252:)
12249:x
12246:(
12238:n
12230:[
12224:2
12221:=
12218:]
12213:n
12205:[
12167:2
12157:1
12134:x
12112:n
12108:}
12104:1
12101:,
12098:1
12092:{
12086:y
12064:n
12060:}
12056:1
12053:,
12050:1
12044:{
12038:x
12015:.
11998:2
11990:1
11984:]
11979:n
11971:[
11935:n
11915:}
11912:1
11909:,
11906:1
11900:{
11892:n
11888:}
11884:1
11881:,
11878:1
11872:{
11864:n
11831:)
11828:n
11818:/
11814:1
11811:(
11808:O
11769:)
11766:n
11762:/
11758:1
11755:(
11730:n
11727:c
11719:p
11697:6
11693:/
11687:3
11683:c
11675:e
11654:)
11651:p
11648:,
11645:n
11642:(
11639:G
11617:n
11613:n
11584:)
11581:n
11577:/
11573:1
11570:(
11567:O
11541:n
11537:c
11534:+
11531:n
11516:p
11492:c
11485:e
11477:e
11456:)
11453:p
11450:,
11447:n
11444:(
11441:G
11409:f
11389:f
11362:]
11359:f
11356:[
11348:3
11344:/
11340:1
11327:4
11324:3
11314:4
11311:3
11289:}
11286:1
11283:,
11280:1
11274:{
11266:n
11262:}
11258:1
11255:,
11252:1
11246:{
11240:f
11202:.
11197:3
11193:)
11189:S
11186:(
11177:f
11169:]
11166:n
11163:[
11157:S
11147:2
11144:1
11139:+
11134:2
11131:1
11106:f
11083:+
11080:2
11076:/
11072:1
11049:)
11043:(
11040:O
11020:f
10994:1
10974:f
10954:)
10951:y
10948:(
10945:f
10942:)
10939:x
10936:(
10933:f
10930:=
10927:)
10924:y
10921:x
10918:(
10915:f
10893:n
10889:}
10885:1
10882:,
10879:1
10873:{
10867:y
10864:,
10861:x
10832:S
10807:)
10802:n
10798:y
10792:n
10788:x
10784:,
10778:,
10773:1
10769:y
10763:1
10759:x
10755:(
10752:=
10749:y
10746:x
10726:)
10723:y
10720:(
10717:f
10714:)
10711:x
10708:(
10705:f
10702:=
10699:)
10696:y
10693:x
10690:(
10687:f
10663:}
10660:1
10657:,
10654:1
10648:{
10640:n
10636:}
10632:1
10629:,
10626:1
10620:{
10614:f
10570:|
10566:]
10563:t
10557:)
10554:g
10551:(
10548:f
10545:[
10536:]
10533:t
10527:)
10524:x
10521:(
10518:f
10515:[
10508:|
10502:t
10473:f
10430:.
10427:)
10419:k
10415:9
10411:k
10408:(
10405:O
10402:=
10398:|
10394:]
10391:)
10388:)
10385:g
10382:(
10379:f
10376:(
10370:[
10362:)
10359:I
10356:,
10353:0
10350:(
10347:N
10341:g
10337:E
10330:]
10327:)
10324:)
10321:x
10318:(
10315:f
10312:(
10306:[
10296:n
10292:}
10288:1
10285:,
10282:1
10276:{
10270:x
10266:E
10261:|
10237:1
10229:2
10225:)
10221:S
10218:(
10209:f
10195:S
10168:2
10164:)
10160:S
10157:(
10148:f
10140:i
10134:S
10124:i
10116:=
10093:f
10084:=
10081:k
10059:S
10051:)
10048:S
10045:(
10036:f
10028:]
10025:n
10022:[
10016:S
10008:=
10005:f
9956:n
9952:}
9948:1
9945:,
9942:1
9936:{
9916:f
9896:f
9874:n
9870:x
9866:,
9860:,
9855:1
9851:x
9830:f
9805:n
9801:}
9797:1
9794:,
9791:1
9785:{
9765:f
9743:i
9739:c
9716:i
9712:x
9706:i
9702:c
9696:n
9691:1
9688:=
9685:i
9677:=
9674:f
9639:p
9633:q
9611:q
9586:p
9563:)
9556:/
9552:]
9549:f
9546:[
9537:(
9491:f
9471:0
9442:M
9436:]
9433:f
9430:[
9404:M
9384:M
9364:}
9361:1
9358:,
9355:1
9349:{
9341:n
9337:}
9333:1
9330:,
9327:1
9321:{
9315:f
9284:.
9281:)
9276:w
9273:,
9268:w
9264:2
9259:x
9244:1
9241:,
9236:w
9232:2
9227:x
9223:(
9211:)
9206:w
9203:,
9200:1
9196:x
9181:1
9178:,
9175:1
9171:x
9167:(
9136:)
9131:n
9127:n
9115:(
9108:=
9105:]
9102:f
9099:[
9091:i
9081:i
9056:f
9027:n
9023:]
9020:f
9017:[
9002:]
8999:f
8996:[
8988:i
8978:i
8950:.
8947:]
8944:f
8941:[
8929:f
8917:]
8914:f
8911:[
8899:]
8896:f
8893:[
8863:R
8854:n
8850:}
8846:1
8843:,
8840:1
8834:{
8828:f
8800:d
8780:)
8774:(
8771:O
8751:f
8723:2
8713:d
8706:f
8682:}
8679:1
8676:,
8673:1
8667:{
8659:n
8655:}
8651:1
8648:,
8645:1
8639:{
8633:f
8611:W
8607:C
8580:d
8576:2
8570:W
8566:C
8545:d
8522:g
8502:)
8496:(
8493:O
8490:=
8487:]
8484:g
8478:f
8475:[
8452:g
8432:)
8426:(
8423:O
8420:=
8415:2
8407:g
8401:f
8378:)
8372:(
8369:O
8349:f
8321:2
8311:1
8304:f
8280:}
8277:1
8274:,
8271:1
8265:{
8257:n
8253:}
8249:1
8246:,
8243:1
8237:{
8231:f
8204:f
8173:f
8153:f
8133:}
8130:1
8127:,
8124:1
8118:{
8110:n
8106:}
8102:1
8099:,
8096:1
8090:{
8084:f
8023:y
8020:,
8017:x
7997:]
7994:)
7991:y
7988:(
7985:f
7982:[
7976:E
7973:=
7970:)
7967:x
7964:(
7961:)
7958:f
7949:U
7945:(
7925:]
7922:)
7919:z
7912:2
7901:1
7896:+
7893:x
7887:(
7884:f
7881:[
7873:)
7870:1
7867:,
7864:0
7861:(
7858:N
7852:z
7848:E
7844:=
7841:)
7838:x
7835:(
7832:)
7829:f
7820:U
7816:(
7794:.
7776:2
7772:L
7740:n
7718:n
7713:R
7685:n
7681:}
7677:1
7674:,
7671:1
7665:{
7626:p
7606:p
7586:f
7566:p
7546:f
7526:f
7504:p
7476:.
7473:]
7468:i
7461:f
7454:f
7451:[
7443:n
7438:1
7435:=
7432:i
7424:=
7418:)
7415:p
7409:1
7406:(
7403:p
7398:]
7395:f
7392:[
7380:=
7377:]
7374:)
7371:x
7368:(
7365:f
7362:[
7352:p
7341:x
7337:E
7330:p
7327:d
7323:d
7298:}
7295:1
7292:,
7289:0
7286:{
7278:n
7274:}
7270:1
7267:,
7264:0
7261:{
7255:f
7224:.
7221:]
7218:)
7215:y
7212:(
7209:f
7206:[
7198:)
7195:x
7192:(
7183:N
7176:y
7172:E
7168:=
7165:)
7162:x
7159:(
7154:S
7146:)
7143:S
7140:(
7131:f
7122:|
7118:S
7114:|
7103:]
7100:n
7097:[
7091:S
7083:=
7080:)
7077:x
7074:(
7071:)
7068:f
7059:T
7055:(
7022:.
7013:1
7001:i
6997:z
6989:,
6974:i
6970:x
6963:{
6958:=
6953:i
6949:y
6919:N
6898:)
6895:x
6892:(
6883:N
6876:y
6854:p
6843:z
6840:,
6837:x
6789:.
6784:2
6780:)
6776:S
6773:(
6764:f
6757:|
6753:S
6749:|
6743:S
6735:=
6732:]
6729:f
6726:[
6718:i
6708:n
6703:1
6700:=
6697:i
6689:=
6686:]
6683:f
6680:[
6648:.
6645:]
6640:2
6636:)
6630:i
6623:f
6616:f
6613:(
6610:[
6604:E
6601:)
6598:p
6592:1
6589:(
6586:p
6583:=
6578:2
6574:)
6570:S
6567:(
6558:f
6550:i
6544:S
6536:=
6533:]
6530:f
6527:[
6519:i
6491:i
6473:p
6456:.
6451:S
6443:)
6440:S
6437:(
6428:f
6420:]
6417:n
6414:[
6408:S
6400:=
6397:f
6384:p
6370:f
6350:f
6340:p
6323:.
6317:|
6313:}
6310:1
6307:=
6302:i
6298:x
6294::
6291:S
6285:i
6282:{
6278:|
6272:)
6265:p
6261:p
6255:1
6244:(
6236:|
6232:}
6229:0
6226:=
6221:i
6217:x
6213::
6210:S
6204:i
6201:{
6197:|
6191:)
6184:p
6178:1
6174:p
6168:(
6163:=
6160:)
6157:x
6154:(
6149:S
6118:p
6112:1
6092:p
6069:.
6064:)
6059:i
6055:x
6048:1
6045:(
6040:i
6031:)
6027:p
6021:1
6018:(
6011:i
6007:x
6001:i
5992:p
5988:=
5985:)
5982:x
5979:(
5974:p
5944:p
5929:p
5915:1
5909:p
5903:0
5881:n
5877:}
5873:1
5870:,
5867:0
5864:{
5844:1
5824:1
5799:n
5795:}
5791:1
5788:,
5785:1
5779:{
5765:p
5744:2
5738:q
5704:.
5695:q
5686:f
5675:2
5667:f
5658:T
5642:2
5634:f
5623:q
5615:f
5606:T
5579:)
5576:q
5572:/
5568:1
5562:1
5559:(
5555:/
5551:1
5548:=
5541:q
5520:2
5514:q
5492:.
5488:|
5484:)
5481:x
5478:(
5475:f
5471:|
5463:n
5459:}
5455:1
5452:,
5449:1
5443:{
5437:x
5429:=
5416:f
5390:.
5384:q
5379:]
5374:q
5369:|
5364:f
5360:|
5356:[
5350:E
5344:=
5339:q
5331:f
5304:R
5295:n
5291:}
5287:1
5284:,
5281:1
5275:{
5269:f
5245:q
5241:L
5213:q
5207:1
5176:f
5167:T
5163:,
5160:f
5154:=
5151:]
5148:f
5145:[
5109:f
5089:x
5064:1
5051:2
5048:1
5020:T
4995:0
4966:.
4961:S
4953:)
4950:S
4947:(
4938:f
4929:|
4925:S
4921:|
4910:]
4907:n
4904:[
4898:S
4890:=
4887:]
4884:)
4881:y
4878:(
4875:f
4872:[
4864:)
4861:x
4858:(
4849:N
4842:y
4838:E
4834:=
4831:)
4828:x
4825:(
4822:)
4819:f
4810:T
4806:(
4782:R
4773:n
4769:}
4765:1
4762:,
4759:1
4753:{
4747:f
4738:T
4716:R
4707:n
4703:}
4699:1
4696:,
4693:1
4687:{
4681:f
4655:T
4603:f
4583:f
4560:.
4557:]
4554:f
4551:[
4540:2
4534:1
4524:2
4521:1
4511:2
4508:1
4503:=
4500:]
4497:f
4494:[
4438:f
4414:1
4402:0
4379:.
4374:2
4370:)
4366:S
4363:(
4354:f
4345:|
4341:S
4337:|
4326:]
4323:n
4320:[
4314:S
4306:=
4303:]
4300:)
4297:y
4294:(
4291:f
4288:)
4285:x
4282:(
4279:f
4276:[
4268:)
4265:x
4262:(
4253:N
4246:y
4243:;
4240:x
4236:E
4232:=
4229:]
4226:f
4223:[
4166:R
4157:n
4153:}
4149:1
4146:,
4143:1
4137:{
4131:f
4104:)
4101:x
4098:(
4089:N
4082:y
4052:.
4047:2
4037:1
4022:i
4018:x
4007:,
4002:2
3995:+
3992:1
3977:i
3973:x
3966:{
3961:=
3956:i
3952:y
3934:.
3925:1
3913:i
3909:z
3901:,
3886:i
3882:x
3875:{
3870:=
3865:i
3861:y
3837:y
3815:n
3811:}
3807:1
3804:,
3801:1
3795:{
3789:z
3786:,
3783:x
3740:=
3737:]
3732:i
3728:y
3722:i
3718:x
3714:[
3708:E
3688:y
3685:,
3682:x
3637:n
3633:}
3629:1
3626:,
3623:1
3617:{
3611:y
3608:,
3605:x
3585:1
3573:1
3543:.
3530:1
3521:|
3517:}
3508:]
3505:f
3502:[
3494:)
3485:1
3482:(
3476:i
3468::
3465:]
3462:n
3459:[
3453:i
3450:{
3446:|
3425:}
3422:1
3419:,
3416:1
3410:{
3402:n
3398:}
3394:1
3391:,
3388:1
3382:{
3379::
3376:f
3353:.
3348:2
3344:)
3340:S
3337:(
3328:f
3320:1
3313:|
3309:S
3305:|
3295:|
3291:S
3287:|
3281:S
3273:=
3270:]
3267:f
3264:[
3242:d
3238:d
3233:=
3230:]
3227:f
3224:[
3216:)
3210:(
3206:I
3179:.
3174:2
3170:)
3166:S
3163:(
3154:f
3146:1
3139:|
3135:S
3131:|
3120:i
3114:S
3106:=
3103:]
3100:f
3092:i
3088:D
3084:[
3068:=
3065:]
3062:f
3059:[
3051:)
3045:(
3039:i
2985:f
2982:L
2979:,
2976:f
2970:=
2967:]
2964:f
2961:[
2924:i
2904:i
2884:f
2853:.
2848:2
2844:)
2840:S
2837:(
2828:f
2821:|
2817:S
2813:|
2807:S
2799:=
2796:]
2793:f
2790:[
2782:i
2772:n
2767:1
2764:=
2761:i
2753:=
2750:]
2747:f
2744:[
2715:f
2688:i
2668:f
2648:0
2645:=
2642:]
2639:f
2636:[
2628:i
2600:.
2597:]
2594:)
2591:x
2588:(
2583:i
2576:f
2569:)
2566:x
2563:(
2560:f
2557:[
2551:=
2548:]
2545:f
2542:[
2534:i
2506:i
2486:]
2483:f
2480:[
2472:i
2447:f
2420:.
2417:)
2412:n
2408:x
2404:,
2398:,
2393:1
2390:+
2387:i
2383:x
2379:,
2374:i
2370:x
2363:,
2358:1
2352:i
2348:x
2344:,
2338:,
2333:1
2329:x
2325:(
2322:f
2319:=
2316:)
2311:n
2307:x
2303:,
2297:,
2292:1
2288:x
2284:(
2279:i
2272:f
2263:,
2258:2
2254:)
2250:S
2247:(
2238:f
2230:i
2224:S
2216:=
2212:]
2207:2
2202:)
2197:2
2191:i
2184:f
2177:f
2171:(
2166:[
2159:E
2156:=
2153:]
2150:f
2147:[
2139:i
2105:R
2096:n
2092:}
2088:1
2085:,
2082:1
2076:{
2070:f
2050:i
2020:d
2013:f
2009:,
2004:d
1997:f
1993:,
1988:d
1981:f
1977:,
1972:d
1965:f
1941:d
1921:f
1898:.
1893:S
1885:)
1882:S
1879:(
1870:f
1862:d
1859:=
1855:|
1851:S
1847:|
1838:=
1833:d
1830:=
1826:f
1802:f
1781:d
1755:|
1751:S
1747:|
1726:)
1723:S
1720:(
1711:f
1681:f
1661:d
1641:S
1621:0
1615:)
1612:S
1609:(
1600:f
1577:d
1556:R
1547:n
1543:}
1539:1
1536:,
1533:1
1527:{
1521:f
1489:.
1484:2
1480:)
1476:S
1473:(
1464:f
1450:S
1442:=
1439:]
1436:f
1433:[
1404:f
1381:=
1378:S
1355:.
1350:2
1346:)
1342:S
1339:(
1330:f
1322:S
1314:=
1311:]
1306:2
1302:f
1298:[
1292:E
1289:=
1284:2
1276:f
1248:n
1244:}
1240:1
1237:,
1234:1
1228:{
1200:]
1197:f
1194:[
1188:E
1185:=
1182:)
1176:(
1167:f
1141:.
1133:S
1125:,
1122:f
1116:=
1113:)
1110:S
1107:(
1098:f
1069:)
1066:x
1063:(
1060:g
1057:)
1054:x
1051:(
1048:f
1041:n
1037:}
1033:1
1030:,
1027:1
1021:{
1015:x
1005:n
998:2
994:=
988:g
985:,
982:f
957:n
953:}
949:1
946:,
943:1
937:{
911:S
886:f
858:)
855:S
852:(
843:f
818:n
813:2
808:Z
779:f
749:.
744:i
740:x
734:S
728:i
720:=
717:)
714:x
711:(
706:S
697:,
694:)
691:x
688:(
683:S
675:)
672:S
669:(
660:f
652:]
649:n
646:[
640:S
632:=
629:)
626:x
623:(
620:f
596:R
587:n
583:}
579:1
576:,
573:1
567:{
561:f
533:}
530:1
527:,
524:0
521:{
501:}
498:1
495:,
492:1
486:{
463:.
460:)
453:n
449:x
444:)
440:1
434:(
431:,
425:,
418:1
414:x
409:)
405:1
399:(
396:(
393:f
390:=
387:)
382:n
378:x
374:,
368:,
363:1
359:x
355:(
346:f
320:n
316:}
312:1
309:,
306:0
303:{
281:n
277:}
273:1
270:,
267:1
261:{
241:f
219:n
215:}
211:1
208:,
205:0
202:{
180:n
176:}
172:1
169:,
166:1
160:{
98:n
94:}
90:1
87:,
84:1
78:{
56:n
52:}
48:1
45:,
42:0
39:{
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
