245:
Nisan and
Szegedy asked whether block sensitivity is polynomially bounded by sensitivity (the other direction is immediate since sensitivity is at most block sensitivity). This is equivalent to asking whether sensitivity is polynomially related to the various decision tree complexity measures, as
1870:. This means that there is a way to assign a sign to every edge of the hypercube so that this property is satisfied. The same signing had been found earlier by Ahmadi et al., which were interested in signings of graphs with few distinct eigenvalues.
1475:
921:
246:
well as to degree, approximate degree, and other complexity measures which have been shown to be polynomially related to these along the years. This became known as the sensitivity conjecture.
249:
Along the years, several special cases of the sensitivity conjecture were proven. The sensitivity theorem was finally proven in its entirety by Huang, using a reduction of
Gotsman and Linial.
1376:
1042:
318:
96:
3071:
210:
2921:
2494:
3376:
1622:
780:
2445:
536:
1690:
4026:
Bafna, Mitali; Lokam, Satyanarayana V.; Tavenas, Sébastien; Velingker, Ameya; Faliszewski, Piotr; Muscholl, Anca; Niedermeier, Rolf (2016). "On the
Sensitivity Conjecture for Read-
2989:
843:
3422:
156:
4525:
3987:
Ahmadi, Bahman; Alinaghipour, Fatemeh; Cavers, Michael S.; Fallat, Shaun; Meagher, Karen; Nasserasr, Shahla (September 2013). "Minimum number of distinct eigenvalues of graphs".
3489:
4057:
Dafni, Neta; Filmus, Yuval; Lifshitz, Noam; Lindzey, Nathan; Vinyals, Marc; Lee, James R. (2021). "Complexity
Measures on the Symmetric Group and Beyond (Extended Abstract)".
3549:
691:
450:
2320:
3319:
1230:
2752:
2021:
566:
3225:
2722:
2555:
2198:
2134:
2045:
1994:
1838:
1794:
1749:
3169:
238:. Nisan and Szegedy showed that degree and approximate degree are also polynomially related to all these measures. Their proof went via yet another complexity measure,
3110:
1950:
2668:
2635:
2284:
2078:
378:
2247:
236:
4552:
2807:
2695:
2602:
951:
482:
3607:
3578:
720:
3275:
2853:
2528:
2343:
1914:
1868:
4572:
3249:
3196:
3130:
2827:
2772:
2575:
2383:
2363:
2218:
2174:
2154:
2098:
1970:
1891:
1814:
1710:
1538:
1518:
1498:
1310:
1290:
1270:
1250:
1186:
1166:
1146:
1126:
1106:
1086:
1062:
971:
646:
626:
606:
586:
405:
346:
4139:
C. S., Karthik; Tavenas, Sébastien; Lal, Akash; Akshay, S.; Saurabh, Saket; Sen, Sandeep (2016). "On the
Sensitivity Conjecture for Disjunctive Normal Forms".
4631:
4166:
Cook, Stephen; Dwork, Cynthia; Reischuk, Rüdiger (1986). "Upper and Lower Time Bounds for
Parallel Random Access Machines without Simultaneous Writes".
1384:
242:, which had been introduced by Nisan. Block sensitivity generalizes a more natural measure, (critical) sensitivity, which had appeared before.
102:, thus settling a conjecture posed by Nisan and Szegedy in 1992. The proof is notably succinct, given that prior progress had been limited.
4332:
4421:
Simon, Hans-Ulrich (1983). "A tight Ω(loglog n)-bound on the time for parallel Ram's to compute nondegenerated boolean functions".
854:
3623:, and proved analogs of the sensitivity theorem for such functions. Their proofs use a reduction to Huang's sensitivity theorem.
4465:
4438:
3977:
111:
1893:
be the signed adjacency matrix corresponding to the signing. The property that the product of the signs in every square is
4425:. Lecture Notes in Computer Science. Vol. 158. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 439–444.
4612:
1318:
984:
260:
38:
3000:
161:
2858:
2450:
4141:
36th IARCS Annual
Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
3327:
1543:
731:
2388:
1128:. If we substitute an arbitrary value in the coordinates not mentioned in the monomial then we get a function
487:
1627:
2937:
791:
3428:
Using this measure, they proved several tight relations between complexity measures of
Boolean functions:
3383:
117:
4478:
3431:
3251:, which is the subgraph of the hypercube consisting of all sensitive edges (edges connecting two points
4292:
Huang, Hao (2019-11-01). "Induced subgraphs of hypercubes and a proof of the
Sensitivity Conjecture".
4110:
Buhrman, Harry; de Wolf, Ronald (2002). "Complexity measures and decision tree complexity: a survey".
3494:
651:
410:
2289:
28:
3280:
1191:
20:
3171:. They showed furthermore that this bound is attained at two neighboring points of the hypercube.
2727:
1999:
541:
3201:
2700:
2533:
2179:
2103:
2026:
1975:
1819:
1754:
1715:
3135:
321:
4392:
Nisan, Noam; Szegedy, Mario (1994). "On the degree of boolean functions as real polynomials".
3079:
1919:
3950:
Aaronson, Scott; Ben-David, Shalev; Kothari, Robin; Rao, Shravas; Tal, Avishay (2021-06-15).
2640:
2607:
2252:
2050:
785:
In the other direction, Tal, improving on an earlier bound of Nisan and
Szegedy, showed that
351:
2226:
215:
4530:
2780:
2673:
2580:
929:
455:
4450:
ITCS '13: Proceedings of the 4th conference on Innovations in Theoretical Computer Science
4448:
Tal, Avishay (2013-01-09). "Properties and applications of boolean function composition".
3583:
3554:
696:
8:
3632:
3254:
2832:
2507:
4032:
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
3612:
Dafni et al. extended the notions of degree and sensitivity to Boolean functions on the
2325:
1896:
1850:
4557:
4301:
3996:
3955:
3620:
3234:
3181:
3115:
2812:
2757:
2560:
2368:
2348:
2203:
2159:
2139:
2083:
1955:
1876:
1799:
1695:
1523:
1503:
1483:
1295:
1275:
1255:
1235:
1171:
1151:
1131:
1111:
1091:
1071:
1047:
956:
631:
611:
591:
571:
390:
331:
4123:
1751:
in which two vertices are connected if they differ by a single coordinate) induced by
4608:
4591:
4461:
4434:
4409:
4380:
4319:
4280:
4248:
4231:
4218:
4213:
4196:
4183:
4154:
4127:
4085:
4072:
4045:
4014:
3973:
3952:
Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem
4583:
4453:
4426:
4401:
4372:
4311:
4270:
4243:
4208:
4175:
4144:
4119:
4098:
4062:
4035:
4006:
3965:
3617:
2220:. (This is a simplification of Huang's original argument due to Shalev Ben-David.)
4149:
4093:
Blum, Manuel; Impagliazzo, Russell (1987). "Generic oracles and oracle classes".
3613:
4344:
Laplante, Sophie; Naserasr, Reza; Sunny, Anupa; Wang, Zhouningxin (2023-03-07).
4315:
4067:
4040:
3915:
4430:
3867:
1470:{\displaystyle g(x_{1},\dots ,x_{n})=f\oplus x_{1}\oplus \cdots \oplus x_{n}.}
4625:
4595:
4413:
4384:
4323:
4284:
4222:
4187:
4158:
4131:
4076:
4049:
4018:
4457:
4275:
4258:
4010:
3969:
3879:
4475:
Tardos, G. (1989). "Query complexity, or why is it difficult to separate
4102:
4587:
4405:
3927:
3816:
1796:. In order to prove the sensitivity theorem, it suffices to show that
3903:
110:
Several papers in the late 1980s and early 1990s showed that various
4376:
4345:
4179:
4095:
28th Annual Symposium on Foundations of Computer Science (sfcs 1987)
3321:). They showed that Huang's proof can be decomposed into two steps:
2754:
for the other, and assign all edges between the two copies the sign
4306:
3960:
3804:
4607:. Stuttgart Chichester New York Brisbane : John Wiley & Sons.
4059:
12th Innovations in Theoretical Computer Science (ITCS) conference
4001:
3828:
3227:. This is the largest eigenvalue of the adjacency matrix of the
3174:
Aaronson, Ben-David, Kothari and Tal defined a new measure, the
3705:
4232:"One-way functions and the nonisomorphism of NP-complete sets"
3986:
3885:
848:
The sensitivity theorem is tight for the AND-of-ORs function:
4333:"Decades-Old Computer Science Conjecture Solved in Two Pages"
3845:
3843:
3756:
1272:. So from now on, we assume without loss of generality that
916:{\displaystyle \bigwedge _{i=1}^{m}\bigvee _{j=1}^{m}x_{ij}}
3949:
3921:
3780:
4257:
Hatami, Pooya; Kulkarni, Raghav; Pankratov, Denis (2011).
4056:
4025:
3933:
3822:
3792:
3693:
3671:
3669:
3667:
2345:
is at most the sum of absolute values of all neighbors of
4343:
3909:
3840:
3744:
3768:
2931:
The sensitivity theorem can be equivalently restated as
4256:
3873:
3810:
3664:
3855:
1847:
in which the product of the signs along any square is
112:
decision tree complexity measures of Boolean functions
16:
Theorem about complexity measures of Boolean functions
4560:
4533:
4481:
4363:
Nisan, Noam (1991). "CREW PRAMs and Decision Trees".
4138:
3891:
3834:
3586:
3557:
3497:
3434:
3386:
3330:
3283:
3257:
3237:
3204:
3184:
3138:
3118:
3082:
3003:
2940:
2861:
2835:
2815:
2783:
2777:
The same signing can also be expressed directly. Let
2760:
2730:
2703:
2676:
2643:
2610:
2583:
2563:
2536:
2510:
2453:
2391:
2371:
2351:
2328:
2292:
2255:
2229:
2206:
2182:
2162:
2142:
2106:
2086:
2053:
2029:
2002:
1978:
1958:
1922:
1899:
1879:
1853:
1822:
1802:
1757:
1718:
1698:
1630:
1546:
1526:
1506:
1486:
1387:
1321:
1298:
1278:
1258:
1238:
1194:
1174:
1154:
1134:
1114:
1094:
1074:
1050:
987:
959:
932:
857:
794:
734:
699:
654:
634:
614:
594:
574:
544:
490:
458:
413:
393:
354:
334:
263:
218:
164:
120:
41:
4229:
3711:
3681:
2530:, we can take an arbitrary signing. Given a signing
3734:
3732:
3654:
3652:
3650:
3648:
4566:
4546:
4519:
3601:
3572:
3543:
3483:
3416:
3370:
3313:
3269:
3243:
3219:
3190:
3163:
3124:
3104:
3065:
2983:
2915:
2847:
2821:
2801:
2766:
2746:
2716:
2689:
2662:
2629:
2596:
2569:
2549:
2522:
2488:
2439:
2377:
2357:
2337:
2314:
2278:
2241:
2212:
2192:
2168:
2148:
2128:
2092:
2072:
2039:
2015:
1988:
1964:
1944:
1908:
1885:
1862:
1832:
1808:
1788:
1743:
1704:
1684:
1616:
1532:
1512:
1492:
1469:
1370:
1304:
1284:
1264:
1244:
1224:
1180:
1160:
1140:
1120:
1108:in the unique multilinear polynomial representing
1100:
1080:
1056:
1036:
965:
945:
915:
837:
774:
714:
685:
640:
620:
600:
580:
560:
530:
476:
444:
399:
372:
340:
312:
230:
204:
150:
90:
4165:
3995:. International Linear Algebra Society: 673–691.
3762:
3717:
348:is the degree of this unique polynomial, denoted
4623:
4086:"Comment #35 to Sensitivity Conjecture resolved"
3729:
3645:
2504:Huang constructed the signing recursively. When
4230:Hartmanis, Juris; Hemachandra, Lane A. (1991).
4092:
3699:
2080:) intersects the space of vectors supported by
1840:. This reduction is due to Gotsman and Linial.
4346:"Sensitivity conjecture and signed hypercubes"
4109:
3798:
1371:{\displaystyle g\colon \{0,1\}^{n}\to \{0,1\}}
1037:{\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}
313:{\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}
91:{\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}
4197:"The equivalence of two problems on the cube"
4194:
3849:
3066:{\displaystyle \deg(f)\leq s_{0}(f)s_{1}(f),}
205:{\displaystyle \alpha (f)\leq C\beta (f)^{C}}
4391:
3786:
3675:
2916:{\displaystyle (-1)^{x_{1}+\cdots +x_{i-1}}}
2489:{\displaystyle \deg _{G}(x)\geq {\sqrt {n}}}
1732:
1719:
1365:
1353:
1341:
1328:
1031:
1019:
1007:
994:
674:
661:
433:
420:
307:
295:
283:
270:
85:
73:
61:
48:
4632:Theorems in computational complexity theory
3371:{\displaystyle \deg(f)\leq \lambda (f)^{2}}
2499:
1617:{\displaystyle |g^{-1}(0)|\neq |g^{-1}(1)|}
775:{\displaystyle s(f)\geq {\sqrt {\deg(f)}}.}
4259:"Variations on the Sensitivity Conjecture"
3580:is the deterministic query complexity and
1232:. If we prove the sensitivity theorem for
114:are polynomially related, meaning that if
4330:
4305:
4274:
4247:
4212:
4201:Journal of Combinatorial Theory, Series A
4148:
4083:
4066:
4039:
4000:
3959:
3897:
3687:
2440:{\displaystyle \deg _{G}(x)\cdot |v_{x}|}
2136:), implying that there is an eigenvector
531:{\displaystyle f(x^{\oplus i})\neq f(x)}
4602:
3750:
4624:
4474:
3723:
1816:has a vertex whose degree is at least
1685:{\displaystyle |g^{-1}(1)|>2^{n-1}}
320:can be expressed in a unique way as a
4420:
4362:
4291:
4195:Gotsman, Chaim; Linial, Nati (1992).
3874:Hatami, Kulkarni & Pankratov 2011
3811:Hatami, Kulkarni & Pankratov 2011
3774:
3738:
3658:
2984:{\displaystyle \deg(f)\leq s(f)^{2}.}
838:{\displaystyle s(f)\leq \deg(f)^{2}.}
3989:Electronic Journal of Linear Algebra
3417:{\displaystyle \lambda (f)\leq s(f)}
1952:, and so half of the eigenvalues of
725:The sensitivity theorem states that
151:{\displaystyle \alpha (f),\beta (f)}
4605:The Complexity of Boolean Functions
4520:{\displaystyle NP^{A}\cap coNP^{A}}
4447:
3861:
3484:{\displaystyle \deg(f)=O(Q(f)^{2})}
2023:. In particular, the eigenspace of
608:'th coordinate. The sensitivity of
98:is at least the square root of its
13:
4331:Klarreich, Erica (July 25, 2019).
14:
4643:
4423:Foundations of Computation Theory
4084:Ben-David, Shalev (3 July 2019).
4061:. p. 5 pages, 326343 bytes.
3609:is the quantum query complexity.
2829:is the first coordinate on which
3712:Hartmanis & Hemachandra 1991
3544:{\displaystyle D(f)=O(Q(f)^{4})}
2994:Laplante et al. refined this to
2809:be an edge of the hypercube. If
1088:, that is, a monomial of degree
1044:be a Boolean function of degree
686:{\displaystyle x\in \{0,1\}^{n}}
445:{\displaystyle x\in \{0,1\}^{n}}
3763:Cook, Dwork & Reischuk 1986
2315:{\displaystyle Av={\sqrt {n}}v}
1712:of the hypercube (the graph on
3596:
3590:
3567:
3561:
3538:
3529:
3522:
3516:
3507:
3501:
3478:
3469:
3462:
3456:
3447:
3441:
3411:
3405:
3396:
3390:
3359:
3352:
3343:
3337:
3308:
3302:
3293:
3287:
3214:
3208:
3158:
3152:
3112:is the maximum sensitivity of
3099:
3093:
3057:
3051:
3038:
3032:
3016:
3010:
2969:
2962:
2953:
2947:
2872:
2862:
2796:
2784:
2473:
2467:
2433:
2418:
2411:
2405:
2272:
2257:
1783:
1777:
1659:
1655:
1649:
1632:
1610:
1606:
1600:
1583:
1575:
1571:
1565:
1548:
1423:
1391:
1350:
1219:
1213:
1204:
1198:
1016:
823:
816:
804:
798:
764:
758:
744:
738:
709:
703:
628:is the maximum sensitivity of
525:
519:
510:
494:
471:
465:
367:
361:
292:
193:
186:
174:
168:
145:
139:
130:
124:
70:
1:
4150:10.4230/LIPICS.FSTTCS.2016.15
4124:10.1016/s0304-3975(01)00144-x
3943:
3314:{\displaystyle f(x)\neq f(y)}
2926:
1225:{\displaystyle s(f)\geq s(F)}
1168:coordinates which has degree
105:
4249:10.1016/0304-3975(91)90323-T
4236:Theoretical Computer Science
4214:10.1016/0097-3165(92)90060-8
4112:Theoretical Computer Science
2747:{\displaystyle -\sigma _{n}}
2604:, we construct a signing of
2016:{\displaystyle -{\sqrt {n}}}
1540:is unbalanced (meaning that
561:{\displaystyle x^{\oplus i}}
252:
7:
4316:10.4007/annals.2019.190.3.6
4207:(1). Elsevier BV: 142–146.
4068:10.4230/LIPICS.ITCS.2021.87
4041:10.4230/LIPICS.MFCS.2016.16
3954:. ACM. pp. 1330–1342.
3700:Blum & Impagliazzo 1987
3626:
3220:{\displaystyle \lambda (f)}
2717:{\displaystyle \sigma _{n}}
2550:{\displaystyle \sigma _{n}}
2193:{\displaystyle {\sqrt {n}}}
2129:{\displaystyle >2^{n-1}}
2040:{\displaystyle {\sqrt {n}}}
1989:{\displaystyle {\sqrt {n}}}
1833:{\displaystyle {\sqrt {n}}}
1789:{\displaystyle S=g^{-1}(1)}
1744:{\displaystyle \{0,1\}^{n}}
1480:It can be shown that since
158:are two such measures then
10:
4648:
3799:Buhrman & de Wolf 2002
4431:10.1007/3-540-12689-9_124
4365:SIAM Journal on Computing
4168:SIAM Journal on Computing
4118:(1). Elsevier BV: 21–43.
3850:Gotsman & Linial 1992
3164:{\displaystyle f^{-1}(b)}
926:This function has degree
452:is the number of indices
31:in 2019, states that the
4394:Computational Complexity
3787:Nisan & Szegedy 1994
3676:Nisan & Szegedy 1994
3638:
3105:{\displaystyle s_{b}(f)}
2855:differ, we use the sign
2500:Constructing the signing
1945:{\displaystyle A^{2}=nI}
1845:signing of the hypercube
1692:. Consider the subgraph
976:
387:of the Boolean function
21:computational complexity
4458:10.1145/2422436.2422485
4276:10.4086/toc.gs.2011.004
4011:10.13001/1081-3810.1679
3970:10.1145/3406325.3451047
2663:{\displaystyle Q_{n+1}}
2630:{\displaystyle Q_{n+1}}
2577:-dimensional hypercube
2279:{\displaystyle |v_{x}|}
2073:{\displaystyle 2^{n-1}}
373:{\displaystyle \deg(f)}
257:Every Boolean function
4603:Wegener, Ingo (1987).
4568:
4548:
4521:
3603:
3574:
3545:
3485:
3418:
3372:
3315:
3271:
3245:
3221:
3192:
3165:
3126:
3106:
3067:
2985:
2917:
2849:
2823:
2803:
2768:
2748:
2718:
2691:
2664:
2637:as follows. Partition
2631:
2598:
2571:
2551:
2524:
2490:
2441:
2379:
2359:
2339:
2316:
2280:
2243:
2242:{\displaystyle x\in S}
2214:
2200:which is supported on
2194:
2170:
2150:
2130:
2094:
2074:
2041:
2017:
1990:
1966:
1946:
1910:
1887:
1864:
1834:
1810:
1790:
1745:
1706:
1686:
1618:
1534:
1514:
1494:
1471:
1372:
1315:Define a new function
1306:
1286:
1266:
1246:
1226:
1182:
1162:
1142:
1122:
1102:
1082:
1058:
1038:
967:
947:
917:
899:
878:
839:
776:
716:
687:
642:
622:
602:
582:
562:
532:
478:
446:
401:
374:
342:
322:multilinear polynomial
314:
232:
231:{\displaystyle C>0}
206:
152:
92:
35:of a Boolean function
4569:
4549:
4547:{\displaystyle P^{A}}
4522:
4294:Annals of Mathematics
3924:, pp. 1330–1342.
3604:
3575:
3546:
3486:
3419:
3373:
3316:
3272:
3246:
3222:
3193:
3166:
3127:
3107:
3068:
2986:
2918:
2850:
2824:
2804:
2802:{\displaystyle (x,y)}
2769:
2749:
2719:
2692:
2690:{\displaystyle Q_{n}}
2665:
2632:
2599:
2597:{\displaystyle Q_{n}}
2572:
2552:
2525:
2491:
2442:
2380:
2360:
2340:
2322:. On the other hand,
2317:
2281:
2244:
2215:
2195:
2171:
2151:
2131:
2100:(which has dimension
2095:
2075:
2047:(which has dimension
2042:
2018:
1991:
1967:
1947:
1911:
1888:
1865:
1835:
1811:
1791:
1746:
1707:
1687:
1619:
1535:
1515:
1495:
1472:
1373:
1307:
1287:
1267:
1247:
1227:
1183:
1163:
1143:
1123:
1103:
1083:
1059:
1039:
968:
948:
946:{\displaystyle m^{2}}
918:
879:
858:
840:
777:
717:
688:
643:
623:
603:
583:
563:
533:
479:
477:{\displaystyle i\in }
447:
402:
375:
343:
315:
233:
207:
153:
93:
4558:
4531:
4479:
4143:. p. 15 pages.
4103:10.1109/sfcs.1987.30
4034:. p. 14 pages.
3922:Aaronson et al. 2021
3910:Laplante et al. 2023
3602:{\displaystyle Q(f)}
3584:
3573:{\displaystyle D(f)}
3555:
3495:
3432:
3384:
3328:
3281:
3255:
3235:
3202:
3182:
3176:spectral sensitivity
3136:
3116:
3080:
3001:
2938:
2859:
2833:
2813:
2781:
2758:
2728:
2724:for one of them and
2701:
2674:
2641:
2608:
2581:
2561:
2534:
2508:
2451:
2389:
2369:
2349:
2326:
2290:
2253:
2227:
2204:
2180:
2160:
2140:
2104:
2084:
2051:
2027:
2000:
1976:
1956:
1920:
1897:
1877:
1851:
1820:
1800:
1755:
1716:
1696:
1628:
1544:
1524:
1504:
1484:
1385:
1319:
1296:
1276:
1256:
1252:then it follows for
1236:
1192:
1172:
1152:
1132:
1112:
1092:
1072:
1048:
985:
957:
930:
855:
792:
732:
715:{\displaystyle s(f)}
697:
652:
632:
612:
592:
572:
542:
488:
456:
411:
391:
352:
332:
261:
216:
162:
118:
39:
4350:Archive ouverte HAL
4263:Theory of Computing
3864:, pp. 441–454.
3777:, pp. 439–444.
3753:, pp. 373–410.
3633:Decision tree model
3270:{\displaystyle x,y}
2848:{\displaystyle x,y}
2670:into two copies of
2523:{\displaystyle n=1}
2385:, which is at most
2286:. On the one hand,
1843:Huang constructs a
25:sensitivity theorem
4588:10.1007/BF02125350
4564:
4554:by random oracles
4544:
4517:
4406:10.1007/BF01263419
3886:Ahmadi et al. 2013
3621:association scheme
3599:
3570:
3541:
3481:
3414:
3368:
3311:
3267:
3241:
3217:
3188:
3161:
3122:
3102:
3063:
2981:
2913:
2845:
2819:
2799:
2764:
2744:
2714:
2687:
2660:
2627:
2594:
2567:
2547:
2520:
2486:
2437:
2375:
2355:
2338:{\displaystyle Av}
2335:
2312:
2276:
2239:
2210:
2190:
2166:
2146:
2126:
2090:
2070:
2037:
2013:
1986:
1962:
1942:
1909:{\displaystyle -1}
1906:
1883:
1863:{\displaystyle -1}
1860:
1830:
1806:
1786:
1741:
1702:
1682:
1614:
1530:
1510:
1490:
1467:
1368:
1302:
1282:
1262:
1242:
1222:
1178:
1158:
1138:
1118:
1098:
1078:
1054:
1034:
963:
943:
913:
835:
772:
712:
683:
638:
618:
598:
578:
558:
528:
474:
442:
397:
370:
338:
310:
228:
212:for some constant
202:
148:
88:
4567:{\displaystyle A}
4467:978-1-4503-1859-4
4440:978-3-540-12689-8
3979:978-1-4503-8053-9
3934:Dafni et al. 2021
3835:C. S. et al. 2016
3823:Bafna et al. 2016
3244:{\displaystyle f}
3229:sensitivity graph
3191:{\displaystyle f}
3125:{\displaystyle f}
2822:{\displaystyle i}
2767:{\displaystyle 1}
2570:{\displaystyle n}
2484:
2378:{\displaystyle S}
2358:{\displaystyle x}
2307:
2223:Consider a point
2213:{\displaystyle S}
2188:
2169:{\displaystyle A}
2149:{\displaystyle v}
2093:{\displaystyle S}
2035:
2011:
1984:
1965:{\displaystyle A}
1886:{\displaystyle A}
1828:
1809:{\displaystyle G}
1705:{\displaystyle G}
1533:{\displaystyle g}
1513:{\displaystyle n}
1493:{\displaystyle f}
1305:{\displaystyle n}
1285:{\displaystyle f}
1265:{\displaystyle f}
1245:{\displaystyle F}
1181:{\displaystyle d}
1161:{\displaystyle d}
1141:{\displaystyle F}
1121:{\displaystyle f}
1101:{\displaystyle d}
1081:{\displaystyle f}
1057:{\displaystyle d}
966:{\displaystyle m}
767:
641:{\displaystyle f}
621:{\displaystyle f}
601:{\displaystyle i}
581:{\displaystyle x}
568:is obtained from
400:{\displaystyle f}
341:{\displaystyle f}
240:block sensitivity
4639:
4618:
4599:
4573:
4571:
4570:
4565:
4553:
4551:
4550:
4545:
4543:
4542:
4526:
4524:
4523:
4518:
4516:
4515:
4494:
4493:
4471:
4444:
4417:
4388:
4359:
4357:
4356:
4340:
4327:
4309:
4288:
4278:
4253:
4251:
4226:
4216:
4191:
4162:
4152:
4135:
4106:
4089:
4080:
4070:
4053:
4043:
4029:
4022:
4004:
3983:
3963:
3937:
3931:
3925:
3919:
3913:
3907:
3901:
3895:
3889:
3883:
3877:
3871:
3865:
3859:
3853:
3847:
3838:
3832:
3826:
3820:
3814:
3808:
3802:
3796:
3790:
3784:
3778:
3772:
3766:
3760:
3754:
3748:
3742:
3736:
3727:
3721:
3715:
3709:
3703:
3697:
3691:
3685:
3679:
3673:
3662:
3656:
3618:perfect matching
3608:
3606:
3605:
3600:
3579:
3577:
3576:
3571:
3550:
3548:
3547:
3542:
3537:
3536:
3490:
3488:
3487:
3482:
3477:
3476:
3423:
3421:
3420:
3415:
3377:
3375:
3374:
3369:
3367:
3366:
3320:
3318:
3317:
3312:
3276:
3274:
3273:
3268:
3250:
3248:
3247:
3242:
3226:
3224:
3223:
3218:
3197:
3195:
3194:
3189:
3170:
3168:
3167:
3162:
3151:
3150:
3131:
3129:
3128:
3123:
3111:
3109:
3108:
3103:
3092:
3091:
3072:
3070:
3069:
3064:
3050:
3049:
3031:
3030:
2990:
2988:
2987:
2982:
2977:
2976:
2922:
2920:
2919:
2914:
2912:
2911:
2910:
2909:
2885:
2884:
2854:
2852:
2851:
2846:
2828:
2826:
2825:
2820:
2808:
2806:
2805:
2800:
2773:
2771:
2770:
2765:
2753:
2751:
2750:
2745:
2743:
2742:
2723:
2721:
2720:
2715:
2713:
2712:
2696:
2694:
2693:
2688:
2686:
2685:
2669:
2667:
2666:
2661:
2659:
2658:
2636:
2634:
2633:
2628:
2626:
2625:
2603:
2601:
2600:
2595:
2593:
2592:
2576:
2574:
2573:
2568:
2556:
2554:
2553:
2548:
2546:
2545:
2529:
2527:
2526:
2521:
2495:
2493:
2492:
2487:
2485:
2480:
2463:
2462:
2446:
2444:
2443:
2438:
2436:
2431:
2430:
2421:
2401:
2400:
2384:
2382:
2381:
2376:
2364:
2362:
2361:
2356:
2344:
2342:
2341:
2336:
2321:
2319:
2318:
2313:
2308:
2303:
2285:
2283:
2282:
2277:
2275:
2270:
2269:
2260:
2248:
2246:
2245:
2240:
2219:
2217:
2216:
2211:
2199:
2197:
2196:
2191:
2189:
2184:
2176:with eigenvalue
2175:
2173:
2172:
2167:
2155:
2153:
2152:
2147:
2135:
2133:
2132:
2127:
2125:
2124:
2099:
2097:
2096:
2091:
2079:
2077:
2076:
2071:
2069:
2068:
2046:
2044:
2043:
2038:
2036:
2031:
2022:
2020:
2019:
2014:
2012:
2007:
1995:
1993:
1992:
1987:
1985:
1980:
1971:
1969:
1968:
1963:
1951:
1949:
1948:
1943:
1932:
1931:
1915:
1913:
1912:
1907:
1892:
1890:
1889:
1884:
1869:
1867:
1866:
1861:
1839:
1837:
1836:
1831:
1829:
1824:
1815:
1813:
1812:
1807:
1795:
1793:
1792:
1787:
1776:
1775:
1750:
1748:
1747:
1742:
1740:
1739:
1711:
1709:
1708:
1703:
1691:
1689:
1688:
1683:
1681:
1680:
1662:
1648:
1647:
1635:
1623:
1621:
1620:
1615:
1613:
1599:
1598:
1586:
1578:
1564:
1563:
1551:
1539:
1537:
1536:
1531:
1519:
1517:
1516:
1511:
1499:
1497:
1496:
1491:
1476:
1474:
1473:
1468:
1463:
1462:
1444:
1443:
1422:
1421:
1403:
1402:
1377:
1375:
1374:
1369:
1349:
1348:
1311:
1309:
1308:
1303:
1291:
1289:
1288:
1283:
1271:
1269:
1268:
1263:
1251:
1249:
1248:
1243:
1231:
1229:
1228:
1223:
1188:, and moreover,
1187:
1185:
1184:
1179:
1167:
1165:
1164:
1159:
1147:
1145:
1144:
1139:
1127:
1125:
1124:
1119:
1107:
1105:
1104:
1099:
1087:
1085:
1084:
1079:
1063:
1061:
1060:
1055:
1043:
1041:
1040:
1035:
1015:
1014:
972:
970:
969:
964:
953:and sensitivity
952:
950:
949:
944:
942:
941:
922:
920:
919:
914:
912:
911:
898:
893:
877:
872:
844:
842:
841:
836:
831:
830:
781:
779:
778:
773:
768:
751:
721:
719:
718:
713:
692:
690:
689:
684:
682:
681:
647:
645:
644:
639:
627:
625:
624:
619:
607:
605:
604:
599:
588:by flipping the
587:
585:
584:
579:
567:
565:
564:
559:
557:
556:
537:
535:
534:
529:
509:
508:
483:
481:
480:
475:
451:
449:
448:
443:
441:
440:
406:
404:
403:
398:
379:
377:
376:
371:
347:
345:
344:
339:
319:
317:
316:
311:
291:
290:
237:
235:
234:
229:
211:
209:
208:
203:
201:
200:
157:
155:
154:
149:
97:
95:
94:
89:
69:
68:
4647:
4646:
4642:
4641:
4640:
4638:
4637:
4636:
4622:
4621:
4615:
4559:
4556:
4555:
4538:
4534:
4532:
4529:
4528:
4511:
4507:
4489:
4485:
4480:
4477:
4476:
4468:
4441:
4377:10.1137/0220062
4371:(6): 999–1007.
4354:
4352:
4337:Quanta Magazine
4180:10.1137/0215006
4027:
3980:
3946:
3941:
3940:
3932:
3928:
3920:
3916:
3908:
3904:
3896:
3892:
3884:
3880:
3872:
3868:
3860:
3856:
3848:
3841:
3833:
3829:
3821:
3817:
3809:
3805:
3797:
3793:
3785:
3781:
3773:
3769:
3761:
3757:
3749:
3745:
3737:
3730:
3722:
3718:
3710:
3706:
3698:
3694:
3686:
3682:
3674:
3665:
3657:
3646:
3641:
3629:
3614:symmetric group
3585:
3582:
3581:
3556:
3553:
3552:
3532:
3528:
3496:
3493:
3492:
3472:
3468:
3433:
3430:
3429:
3385:
3382:
3381:
3362:
3358:
3329:
3326:
3325:
3282:
3279:
3278:
3256:
3253:
3252:
3236:
3233:
3232:
3203:
3200:
3199:
3183:
3180:
3179:
3143:
3139:
3137:
3134:
3133:
3117:
3114:
3113:
3087:
3083:
3081:
3078:
3077:
3045:
3041:
3026:
3022:
3002:
2999:
2998:
2972:
2968:
2939:
2936:
2935:
2929:
2899:
2895:
2880:
2876:
2875:
2871:
2860:
2857:
2856:
2834:
2831:
2830:
2814:
2811:
2810:
2782:
2779:
2778:
2759:
2756:
2755:
2738:
2734:
2729:
2726:
2725:
2708:
2704:
2702:
2699:
2698:
2681:
2677:
2675:
2672:
2671:
2648:
2644:
2642:
2639:
2638:
2615:
2611:
2609:
2606:
2605:
2588:
2584:
2582:
2579:
2578:
2562:
2559:
2558:
2541:
2537:
2535:
2532:
2531:
2509:
2506:
2505:
2502:
2479:
2458:
2454:
2452:
2449:
2448:
2432:
2426:
2422:
2417:
2396:
2392:
2390:
2387:
2386:
2370:
2367:
2366:
2350:
2347:
2346:
2327:
2324:
2323:
2302:
2291:
2288:
2287:
2271:
2265:
2261:
2256:
2254:
2251:
2250:
2228:
2225:
2224:
2205:
2202:
2201:
2183:
2181:
2178:
2177:
2161:
2158:
2157:
2141:
2138:
2137:
2114:
2110:
2105:
2102:
2101:
2085:
2082:
2081:
2058:
2054:
2052:
2049:
2048:
2030:
2028:
2025:
2024:
2006:
2001:
1998:
1997:
1979:
1977:
1974:
1973:
1957:
1954:
1953:
1927:
1923:
1921:
1918:
1917:
1898:
1895:
1894:
1878:
1875:
1874:
1852:
1849:
1848:
1823:
1821:
1818:
1817:
1801:
1798:
1797:
1768:
1764:
1756:
1753:
1752:
1735:
1731:
1717:
1714:
1713:
1697:
1694:
1693:
1670:
1666:
1658:
1640:
1636:
1631:
1629:
1626:
1625:
1609:
1591:
1587:
1582:
1574:
1556:
1552:
1547:
1545:
1542:
1541:
1525:
1522:
1521:
1505:
1502:
1501:
1485:
1482:
1481:
1458:
1454:
1439:
1435:
1417:
1413:
1398:
1394:
1386:
1383:
1382:
1344:
1340:
1320:
1317:
1316:
1297:
1294:
1293:
1277:
1274:
1273:
1257:
1254:
1253:
1237:
1234:
1233:
1193:
1190:
1189:
1173:
1170:
1169:
1153:
1150:
1149:
1133:
1130:
1129:
1113:
1110:
1109:
1093:
1090:
1089:
1073:
1070:
1069:
1064:. Consider any
1049:
1046:
1045:
1010:
1006:
986:
983:
982:
979:
958:
955:
954:
937:
933:
931:
928:
927:
904:
900:
894:
883:
873:
862:
856:
853:
852:
826:
822:
793:
790:
789:
750:
733:
730:
729:
698:
695:
694:
677:
673:
653:
650:
649:
633:
630:
629:
613:
610:
609:
593:
590:
589:
573:
570:
569:
549:
545:
543:
540:
539:
501:
497:
489:
486:
485:
457:
454:
453:
436:
432:
412:
409:
408:
392:
389:
388:
353:
350:
349:
333:
330:
329:
286:
282:
262:
259:
258:
255:
217:
214:
213:
196:
192:
163:
160:
159:
119:
116:
115:
108:
64:
60:
40:
37:
36:
17:
12:
11:
5:
4645:
4635:
4634:
4620:
4619:
4613:
4600:
4582:(4): 385–392.
4563:
4541:
4537:
4514:
4510:
4506:
4503:
4500:
4497:
4492:
4488:
4484:
4472:
4466:
4445:
4439:
4418:
4400:(4): 301–313.
4389:
4360:
4341:
4328:
4289:
4254:
4242:(1): 155–163.
4227:
4192:
4163:
4136:
4107:
4090:
4081:
4054:
4023:
3984:
3978:
3945:
3942:
3939:
3938:
3926:
3914:
3902:
3898:Ben-David 2019
3890:
3878:
3876:, Example 5.2.
3866:
3854:
3839:
3827:
3815:
3803:
3791:
3789:, p. 311.
3779:
3767:
3755:
3743:
3728:
3716:
3704:
3692:
3688:Klarreich 2019
3680:
3663:
3643:
3642:
3640:
3637:
3636:
3635:
3628:
3625:
3598:
3595:
3592:
3589:
3569:
3566:
3563:
3560:
3540:
3535:
3531:
3527:
3524:
3521:
3518:
3515:
3512:
3509:
3506:
3503:
3500:
3480:
3475:
3471:
3467:
3464:
3461:
3458:
3455:
3452:
3449:
3446:
3443:
3440:
3437:
3426:
3425:
3413:
3410:
3407:
3404:
3401:
3398:
3395:
3392:
3389:
3379:
3365:
3361:
3357:
3354:
3351:
3348:
3345:
3342:
3339:
3336:
3333:
3310:
3307:
3304:
3301:
3298:
3295:
3292:
3289:
3286:
3266:
3263:
3260:
3240:
3216:
3213:
3210:
3207:
3187:
3160:
3157:
3154:
3149:
3146:
3142:
3132:at a point in
3121:
3101:
3098:
3095:
3090:
3086:
3074:
3073:
3062:
3059:
3056:
3053:
3048:
3044:
3040:
3037:
3034:
3029:
3025:
3021:
3018:
3015:
3012:
3009:
3006:
2992:
2991:
2980:
2975:
2971:
2967:
2964:
2961:
2958:
2955:
2952:
2949:
2946:
2943:
2928:
2925:
2908:
2905:
2902:
2898:
2894:
2891:
2888:
2883:
2879:
2874:
2870:
2867:
2864:
2844:
2841:
2838:
2818:
2798:
2795:
2792:
2789:
2786:
2763:
2741:
2737:
2733:
2711:
2707:
2684:
2680:
2657:
2654:
2651:
2647:
2624:
2621:
2618:
2614:
2591:
2587:
2566:
2544:
2540:
2519:
2516:
2513:
2501:
2498:
2483:
2478:
2475:
2472:
2469:
2466:
2461:
2457:
2435:
2429:
2425:
2420:
2416:
2413:
2410:
2407:
2404:
2399:
2395:
2374:
2354:
2334:
2331:
2311:
2306:
2301:
2298:
2295:
2274:
2268:
2264:
2259:
2238:
2235:
2232:
2209:
2187:
2165:
2145:
2123:
2120:
2117:
2113:
2109:
2089:
2067:
2064:
2061:
2057:
2034:
2010:
2005:
1983:
1961:
1941:
1938:
1935:
1930:
1926:
1905:
1902:
1882:
1859:
1856:
1827:
1805:
1785:
1782:
1779:
1774:
1771:
1767:
1763:
1760:
1738:
1734:
1730:
1727:
1724:
1721:
1701:
1679:
1676:
1673:
1669:
1665:
1661:
1657:
1654:
1651:
1646:
1643:
1639:
1634:
1612:
1608:
1605:
1602:
1597:
1594:
1590:
1585:
1581:
1577:
1573:
1570:
1567:
1562:
1559:
1555:
1550:
1529:
1509:
1489:
1478:
1477:
1466:
1461:
1457:
1453:
1450:
1447:
1442:
1438:
1434:
1431:
1428:
1425:
1420:
1416:
1412:
1409:
1406:
1401:
1397:
1393:
1390:
1367:
1364:
1361:
1358:
1355:
1352:
1347:
1343:
1339:
1336:
1333:
1330:
1327:
1324:
1301:
1281:
1261:
1241:
1221:
1218:
1215:
1212:
1209:
1206:
1203:
1200:
1197:
1177:
1157:
1137:
1117:
1097:
1077:
1053:
1033:
1030:
1027:
1024:
1021:
1018:
1013:
1009:
1005:
1002:
999:
996:
993:
990:
978:
975:
962:
940:
936:
924:
923:
910:
907:
903:
897:
892:
889:
886:
882:
876:
871:
868:
865:
861:
846:
845:
834:
829:
825:
821:
818:
815:
812:
809:
806:
803:
800:
797:
783:
782:
771:
766:
763:
760:
757:
754:
749:
746:
743:
740:
737:
711:
708:
705:
702:
680:
676:
672:
669:
666:
663:
660:
657:
637:
617:
597:
577:
555:
552:
548:
527:
524:
521:
518:
515:
512:
507:
504:
500:
496:
493:
473:
470:
467:
464:
461:
439:
435:
431:
428:
425:
422:
419:
416:
396:
369:
366:
363:
360:
357:
337:
309:
306:
303:
300:
297:
294:
289:
285:
281:
278:
275:
272:
269:
266:
254:
251:
227:
224:
221:
199:
195:
191:
188:
185:
182:
179:
176:
173:
170:
167:
147:
144:
141:
138:
135:
132:
129:
126:
123:
107:
104:
87:
84:
81:
78:
75:
72:
67:
63:
59:
56:
53:
50:
47:
44:
15:
9:
6:
4:
3:
2:
4644:
4633:
4630:
4629:
4627:
4616:
4614:0-471-91555-6
4610:
4606:
4601:
4597:
4593:
4589:
4585:
4581:
4577:
4576:Combinatorica
4561:
4539:
4535:
4512:
4508:
4504:
4501:
4498:
4495:
4490:
4486:
4482:
4473:
4469:
4463:
4459:
4455:
4451:
4446:
4442:
4436:
4432:
4428:
4424:
4419:
4415:
4411:
4407:
4403:
4399:
4395:
4390:
4386:
4382:
4378:
4374:
4370:
4366:
4361:
4351:
4347:
4342:
4338:
4334:
4329:
4325:
4321:
4317:
4313:
4308:
4303:
4299:
4295:
4290:
4286:
4282:
4277:
4272:
4268:
4264:
4260:
4255:
4250:
4245:
4241:
4237:
4233:
4228:
4224:
4220:
4215:
4210:
4206:
4202:
4198:
4193:
4189:
4185:
4181:
4177:
4173:
4169:
4164:
4160:
4156:
4151:
4146:
4142:
4137:
4133:
4129:
4125:
4121:
4117:
4113:
4108:
4104:
4100:
4096:
4091:
4087:
4082:
4078:
4074:
4069:
4064:
4060:
4055:
4051:
4047:
4042:
4037:
4033:
4024:
4020:
4016:
4012:
4008:
4003:
3998:
3994:
3990:
3985:
3981:
3975:
3971:
3967:
3962:
3957:
3953:
3948:
3947:
3935:
3930:
3923:
3918:
3911:
3906:
3899:
3894:
3887:
3882:
3875:
3870:
3863:
3858:
3851:
3846:
3844:
3836:
3831:
3824:
3819:
3812:
3807:
3800:
3795:
3788:
3783:
3776:
3771:
3764:
3759:
3752:
3747:
3740:
3735:
3733:
3725:
3720:
3713:
3708:
3701:
3696:
3689:
3684:
3677:
3672:
3670:
3668:
3660:
3655:
3653:
3651:
3649:
3644:
3634:
3631:
3630:
3624:
3622:
3619:
3615:
3610:
3593:
3587:
3564:
3558:
3533:
3525:
3519:
3513:
3510:
3504:
3498:
3473:
3465:
3459:
3453:
3450:
3444:
3438:
3435:
3408:
3402:
3399:
3393:
3387:
3380:
3363:
3355:
3349:
3346:
3340:
3334:
3331:
3324:
3323:
3322:
3305:
3299:
3296:
3290:
3284:
3264:
3261:
3258:
3238:
3230:
3211:
3205:
3185:
3177:
3172:
3155:
3147:
3144:
3140:
3119:
3096:
3088:
3084:
3060:
3054:
3046:
3042:
3035:
3027:
3023:
3019:
3013:
3007:
3004:
2997:
2996:
2995:
2978:
2973:
2965:
2959:
2956:
2950:
2944:
2941:
2934:
2933:
2932:
2924:
2906:
2903:
2900:
2896:
2892:
2889:
2886:
2881:
2877:
2868:
2865:
2842:
2839:
2836:
2816:
2793:
2790:
2787:
2775:
2761:
2739:
2735:
2731:
2709:
2705:
2682:
2678:
2655:
2652:
2649:
2645:
2622:
2619:
2616:
2612:
2589:
2585:
2564:
2542:
2538:
2517:
2514:
2511:
2497:
2481:
2476:
2470:
2464:
2459:
2455:
2427:
2423:
2414:
2408:
2402:
2397:
2393:
2372:
2352:
2332:
2329:
2309:
2304:
2299:
2296:
2293:
2266:
2262:
2236:
2233:
2230:
2221:
2207:
2185:
2163:
2143:
2121:
2118:
2115:
2111:
2107:
2087:
2065:
2062:
2059:
2055:
2032:
2008:
2003:
1996:and half are
1981:
1959:
1939:
1936:
1933:
1928:
1924:
1916:implies that
1903:
1900:
1880:
1871:
1857:
1854:
1846:
1841:
1825:
1803:
1780:
1772:
1769:
1765:
1761:
1758:
1736:
1728:
1725:
1722:
1699:
1677:
1674:
1671:
1667:
1663:
1652:
1644:
1641:
1637:
1603:
1595:
1592:
1588:
1579:
1568:
1560:
1557:
1553:
1527:
1507:
1487:
1464:
1459:
1455:
1451:
1448:
1445:
1440:
1436:
1432:
1429:
1426:
1418:
1414:
1410:
1407:
1404:
1399:
1395:
1388:
1381:
1380:
1379:
1362:
1359:
1356:
1345:
1337:
1334:
1331:
1325:
1322:
1313:
1299:
1279:
1259:
1239:
1216:
1210:
1207:
1201:
1195:
1175:
1155:
1135:
1115:
1095:
1075:
1067:
1051:
1028:
1025:
1022:
1011:
1003:
1000:
997:
991:
988:
974:
960:
938:
934:
908:
905:
901:
895:
890:
887:
884:
880:
874:
869:
866:
863:
859:
851:
850:
849:
832:
827:
819:
813:
810:
807:
801:
795:
788:
787:
786:
769:
761:
755:
752:
747:
741:
735:
728:
727:
726:
723:
706:
700:
678:
670:
667:
664:
658:
655:
648:at any point
635:
615:
595:
575:
553:
550:
546:
522:
516:
513:
505:
502:
498:
491:
468:
462:
459:
437:
429:
426:
423:
417:
414:
407:at the point
394:
386:
381:
364:
358:
355:
335:
327:
323:
304:
301:
298:
287:
279:
276:
273:
267:
264:
250:
247:
243:
241:
225:
222:
219:
197:
189:
183:
180:
177:
171:
165:
142:
136:
133:
127:
121:
113:
103:
101:
82:
79:
76:
65:
57:
54:
51:
45:
42:
34:
30:
26:
22:
4604:
4579:
4575:
4449:
4422:
4397:
4393:
4368:
4364:
4353:. Retrieved
4349:
4336:
4297:
4293:
4266:
4262:
4239:
4235:
4204:
4200:
4174:(1): 87–97.
4171:
4167:
4140:
4115:
4111:
4094:
4058:
4031:
3992:
3988:
3951:
3929:
3917:
3905:
3893:
3881:
3869:
3857:
3830:
3818:
3806:
3794:
3782:
3770:
3758:
3751:Wegener 1987
3746:
3719:
3707:
3695:
3683:
3611:
3427:
3228:
3175:
3173:
3075:
2993:
2930:
2776:
2503:
2222:
1872:
1844:
1842:
1479:
1314:
1065:
980:
925:
847:
784:
724:
384:
382:
325:
256:
248:
244:
239:
109:
99:
32:
27:, proved by
24:
18:
4269:(1): 1–27.
4030:Formulas".
3724:Tardos 1989
3616:and on the
2249:maximizing
1500:has degree
1292:has degree
385:sensitivity
33:sensitivity
4355:2024-04-25
4307:1907.00847
3961:2010.12629
3944:References
3775:Simon 1983
3739:Nisan 1991
3659:Huang 2019
3277:such that
3198:, denoted
2927:Extensions
1066:maxonomial
693:, denoted
484:such that
106:Background
4596:0209-9683
4496:∩
4414:1016-3328
4385:0097-5397
4324:0003-486X
4285:1557-2862
4223:0097-3165
4188:0097-5397
4159:1868-8969
4132:0304-3975
4077:1868-8969
4050:1868-8969
4019:1081-3810
4002:1304.1205
3439:
3400:≤
3388:λ
3350:λ
3347:≤
3335:
3297:≠
3206:λ
3145:−
3020:≤
3008:
2957:≤
2945:
2904:−
2890:⋯
2866:−
2736:σ
2732:−
2706:σ
2539:σ
2477:≥
2465:
2415:⋅
2403:
2234:∈
2119:−
2063:−
2004:−
1901:−
1855:−
1770:−
1675:−
1642:−
1593:−
1580:≠
1558:−
1452:⊕
1449:⋯
1446:⊕
1433:⊕
1408:…
1351:→
1326::
1208:≥
1017:→
992::
881:⋁
860:⋀
814:
808:≤
756:
748:≥
659:∈
551:⊕
514:≠
503:⊕
463:∈
418:∈
359:
293:→
268::
253:Statement
184:β
178:≤
166:α
137:β
122:α
71:→
46::
29:Hao Huang
4626:Category
4097:. IEEE.
3862:Tal 2013
3627:See also
2447:. Hence
538:, where
4452:. ACM.
3551:. Here
2557:of the
1624:), say
4611:
4594:
4464:
4437:
4412:
4383:
4322:
4283:
4221:
4186:
4157:
4130:
4075:
4048:
4017:
3976:
3076:where
2697:. Use
326:degree
324:. The
100:degree
23:, the
4527:from
4302:arXiv
4300:(3).
3997:arXiv
3956:arXiv
3639:Notes
1520:then
977:Proof
4609:ISBN
4592:ISSN
4574:?".
4462:ISBN
4435:ISBN
4410:ISSN
4381:ISSN
4320:ISSN
4281:ISSN
4219:ISSN
4184:ISSN
4155:ISSN
4128:ISSN
4073:ISSN
4046:ISSN
4015:ISSN
3974:ISBN
3491:and
2108:>
1972:are
1873:Let
1664:>
981:Let
383:The
223:>
4584:doi
4454:doi
4427:doi
4402:doi
4373:doi
4312:doi
4298:190
4271:doi
4244:doi
4209:doi
4176:doi
4145:doi
4120:doi
4116:288
4099:doi
4063:doi
4036:doi
4007:doi
3966:doi
3436:deg
3332:deg
3231:of
3178:of
3005:deg
2942:deg
2456:deg
2394:deg
2365:in
2156:of
1378:by
1148:on
1068:of
811:deg
753:deg
356:deg
328:of
19:In
4628::
4590:.
4578:.
4460:.
4433:.
4408:.
4396:.
4379:.
4369:20
4367:.
4348:.
4335:.
4318:.
4310:.
4296:.
4279:.
4265:.
4261:.
4240:81
4238:.
4234:.
4217:.
4205:61
4203:.
4199:.
4182:.
4172:15
4170:.
4153:.
4126:.
4114:.
4071:.
4044:.
4013:.
4005:.
3993:26
3991:.
3972:.
3964:.
3842:^
3731:^
3666:^
3647:^
2923:.
2774:.
2496:.
1312:.
973:.
722:.
380:.
4617:.
4598:.
4586::
4580:9
4562:A
4540:A
4536:P
4513:A
4509:P
4505:N
4502:o
4499:c
4491:A
4487:P
4483:N
4470:.
4456::
4443:.
4429::
4416:.
4404::
4398:4
4387:.
4375::
4358:.
4339:.
4326:.
4314::
4304::
4287:.
4273::
4267:1
4252:.
4246::
4225:.
4211::
4190:.
4178::
4161:.
4147::
4134:.
4122::
4105:.
4101::
4088:.
4079:.
4065::
4052:.
4038::
4028:k
4021:.
4009::
3999::
3982:.
3968::
3958::
3936:.
3912:.
3900:.
3888:.
3852:.
3837:.
3825:.
3813:.
3801:.
3765:.
3741:.
3726:.
3714:.
3702:.
3690:.
3678:.
3661:.
3597:)
3594:f
3591:(
3588:Q
3568:)
3565:f
3562:(
3559:D
3539:)
3534:4
3530:)
3526:f
3523:(
3520:Q
3517:(
3514:O
3511:=
3508:)
3505:f
3502:(
3499:D
3479:)
3474:2
3470:)
3466:f
3463:(
3460:Q
3457:(
3454:O
3451:=
3448:)
3445:f
3442:(
3424:.
3412:)
3409:f
3406:(
3403:s
3397:)
3394:f
3391:(
3378:.
3364:2
3360:)
3356:f
3353:(
3344:)
3341:f
3338:(
3309:)
3306:y
3303:(
3300:f
3294:)
3291:x
3288:(
3285:f
3265:y
3262:,
3259:x
3239:f
3215:)
3212:f
3209:(
3186:f
3159:)
3156:b
3153:(
3148:1
3141:f
3120:f
3100:)
3097:f
3094:(
3089:b
3085:s
3061:,
3058:)
3055:f
3052:(
3047:1
3043:s
3039:)
3036:f
3033:(
3028:0
3024:s
3017:)
3014:f
3011:(
2979:.
2974:2
2970:)
2966:f
2963:(
2960:s
2954:)
2951:f
2948:(
2907:1
2901:i
2897:x
2893:+
2887:+
2882:1
2878:x
2873:)
2869:1
2863:(
2843:y
2840:,
2837:x
2817:i
2797:)
2794:y
2791:,
2788:x
2785:(
2762:1
2740:n
2710:n
2683:n
2679:Q
2656:1
2653:+
2650:n
2646:Q
2623:1
2620:+
2617:n
2613:Q
2590:n
2586:Q
2565:n
2543:n
2518:1
2515:=
2512:n
2482:n
2474:)
2471:x
2468:(
2460:G
2434:|
2428:x
2424:v
2419:|
2412:)
2409:x
2406:(
2398:G
2373:S
2353:x
2333:v
2330:A
2310:v
2305:n
2300:=
2297:v
2294:A
2273:|
2267:x
2263:v
2258:|
2237:S
2231:x
2208:S
2186:n
2164:A
2144:v
2122:1
2116:n
2112:2
2088:S
2066:1
2060:n
2056:2
2033:n
2009:n
1982:n
1960:A
1940:I
1937:n
1934:=
1929:2
1925:A
1904:1
1881:A
1858:1
1826:n
1804:G
1784:)
1781:1
1778:(
1773:1
1766:g
1762:=
1759:S
1737:n
1733:}
1729:1
1726:,
1723:0
1720:{
1700:G
1678:1
1672:n
1668:2
1660:|
1656:)
1653:1
1650:(
1645:1
1638:g
1633:|
1611:|
1607:)
1604:1
1601:(
1596:1
1589:g
1584:|
1576:|
1572:)
1569:0
1566:(
1561:1
1554:g
1549:|
1528:g
1508:n
1488:f
1465:.
1460:n
1456:x
1441:1
1437:x
1430:f
1427:=
1424:)
1419:n
1415:x
1411:,
1405:,
1400:1
1396:x
1392:(
1389:g
1366:}
1363:1
1360:,
1357:0
1354:{
1346:n
1342:}
1338:1
1335:,
1332:0
1329:{
1323:g
1300:n
1280:f
1260:f
1240:F
1220:)
1217:F
1214:(
1211:s
1205:)
1202:f
1199:(
1196:s
1176:d
1156:d
1136:F
1116:f
1096:d
1076:f
1052:d
1032:}
1029:1
1026:,
1023:0
1020:{
1012:n
1008:}
1004:1
1001:,
998:0
995:{
989:f
961:m
939:2
935:m
909:j
906:i
902:x
896:m
891:1
888:=
885:j
875:m
870:1
867:=
864:i
833:.
828:2
824:)
820:f
817:(
805:)
802:f
799:(
796:s
770:.
765:)
762:f
759:(
745:)
742:f
739:(
736:s
710:)
707:f
704:(
701:s
679:n
675:}
671:1
668:,
665:0
662:{
656:x
636:f
616:f
596:i
576:x
554:i
547:x
526:)
523:x
520:(
517:f
511:)
506:i
499:x
495:(
492:f
472:]
469:n
466:[
460:i
438:n
434:}
430:1
427:,
424:0
421:{
415:x
395:f
368:)
365:f
362:(
336:f
308:}
305:1
302:,
299:0
296:{
288:n
284:}
280:1
277:,
274:0
271:{
265:f
226:0
220:C
198:C
194:)
190:f
187:(
181:C
175:)
172:f
169:(
146:)
143:f
140:(
134:,
131:)
128:f
125:(
86:}
83:1
80:,
77:0
74:{
66:n
62:}
58:1
55:,
52:0
49:{
43:f
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.