22:
4601:, so the conjecture is specifically concerned about finding a lower bound for sensitivity. Since all of the previously-discussed complexity measures are polynomially related, the precise type of complexity measure is not relevant. However, this is typically phrased as the question of relating sensitivity with block sensitivity.
60:) and can be performed quickly (say, with unit computational cost), so the worst-case time complexity of an algorithm in the decision tree model corresponds to the depth of the corresponding decision tree. This notion of computational complexity of a problem or an algorithm in the decision tree model is called its
461:
These algorithms can be modeled as binary decision trees, where the queries are comparisons: an internal node corresponds to a query, and the node's children correspond to the next query when the answer to the question is yes or no. For leaf nodes, the output corresponds to a
1780:. Another equivalent definition is to define it as a distribution over deterministic decision trees. Based on this second definition, the complexity of the randomized tree is defined as the largest depth among all the trees in the support of the underlying distribution.
3481:
718:
This argument does not use anything about the type of query, so it in fact proves a lower bound for any sorting algorithm that can be modeled as a binary decision tree. In essence, this is a rephrasing of the
1013:
3310:
3858:
3560:
705:
1560:. Each query may be dependent on previous queries. There are many types of computational models using decision trees that could be considered, admitting multiple complexity notions, called
1217:
4816:
707:, so this is a lower bound on the run time of a comparison sorting algorithm. In this case, the existence of numerous comparison-sorting algorithms having this time complexity, such as
296:
4191:
1457:
5589:
Aaronson, Scott; Ben-David, Shalev; Kothari, Robin; Rao, Shravas; Tal, Avishay (2020-10-23). "Degree vs. Approximate Degree and
Quantum Implications of Huang's Sensitivity Theorem".
2977:
4555:
3242:
3621:
894:
3992:
3925:
3759:
3692:
940:
4989:
1356:
560:
4490:
2915:
2512:
2182:
1918:
1644:
1502:
582:
elements; otherwise, the algorithm would fail for that particular permutation as input. So, its corresponding decision tree must have at least as many leaves as permutations:
456:
416:
336:
4599:
763:
4042:
2222:
1312:
1107:
376:
4410:
2870:
2292:
2137:
788:
numbers. Before the smallest number can be determined, every number except the smallest must "lose" (compare greater) in at least one comparison. So, it takes at least
513:
4078:
3142:
3052:
2747:
2711:
2671:
2635:
2549:
2409:
2045:
2003:
1957:
1815:
143:
2806:
844:
3177:
3087:
2248:
222:
196:
4890:
4843:
4658:
2364:
1778:
1529:
1383:
1067:
1040:
170:
4919:
4344:
4107:
2579:
2439:
1845:
1694:
1599:
1558:
1246:
768:
Other decision tree lower bounds do use that the query is a comparison. For example, consider the task of only using comparisons to find the smallest number among
483:
2467:
1873:
1272:
812:
626:
603:
4863:
4758:
4738:
4718:
4698:
4678:
4626:
4430:
4372:
4315:
4295:
4275:
4255:
4235:
4215:
3358:
3338:
2997:
2939:
2826:
2774:
2599:
2332:
2312:
2105:
2085:
1739:
1719:
1664:
1157:
1127:
786:
580:
108:
3565:
All of these types of query complexity are polynomially related. Blum and
Impagliazzo, Hartmanis and Hemachandra, and Tardos independently discovered that
2677:, because the direct definition of a quantum decision tree is more complicated than in the classical case. Similar to the randomized case, we define
3363:
1015:. (Algorithms in this model can only depend on the sign of the output.) Comparison trees are linear decision trees, because the comparison between
79:
for certain classes of computational problems and algorithms. Several variants of decision tree models have been introduced, depending on the
232:
Decision trees are often employed to understand algorithms for sorting and other similar problems; this was first done by Ford and
Johnson.
2010:
depth of a decision tree that must be correct (i.e., has zero-error). There is also a one-sided bounded-error version which is denoted by
5712:
224:. Comparison sorts can be expressed as a decision tree in this model, since such sorting algorithms only perform these types of queries.
5010:
3627:
found that the Monte Carlo randomized decision tree complexity is also polynomially related to deterministic decision tree complexity:
5778:
5519:
Kulkarni, R. and Tal, A. On
Fractional Block Sensitivity. Electronic Colloquium on Computational Complexity (ECCC). Vol. 20. 2013.
945:
562:
comparisons through a simple argument: for an algorithm to be correct, it must be able to output every possible permutation of
5269:
5087:
3247:
485:
that describes how the input sequence was scrambled from the fully ordered list of items. (The inverse of this permutation,
3764:
3486:
1385:
lower bound for linear decision trees on the knapsack problem, generalized to algebraic decision trees by Steele and Yao.
631:
418:. Assuming that the items to be sorted are all distinct and comparable, this can be rephrased as a yes-or-no question: is
1666:. The depth of a tree is the maximum number of queries that can happen before a leaf is reached and a result obtained.
1964:
randomized decision-tree complexity, because the result is allowed to be incorrect with bounded two-sided error. The
5226:
1169:
765:
bits of information about the input sequence. As a result, this also works for randomized decision trees as well.
5532:
Ambainis, Andris; Balodis, Kaspars; Belovs, Aleksandrs; Lee, Troy; Santha, Miklos; Smotrovs, Juris (2017-09-04).
5434:
Hartmanis, J.; Hemachandra, L. (1987), "One-way functions, robustness, and non-isomorphism of NP-complete sets",
4763:
76:
30:
5783:
4381:
is the conjecture that sensitivity is polynomially related to query complexity; that is, there exists exponent
242:
4133:
1399:
4347:
2944:
5015:
3562:. Finding the best upper bounds in the converse direction is a major goal in the field of query complexity.
3185:
3568:
896:
as input. The tests in linear decision trees are linear functions: for a particular choice of real numbers
864:
858:
Linear decision trees generalize the above comparison decision trees to computing functions that take real
3930:
3863:
3697:
3630:
2334:. The analogous notion where one only requires the verifier to be correct with 2/3 probability is denoted
5374:
Beals, R.; Buhrman, H.; Cleve, R.; Mosca, M.; de Wolf, R. (2001). "Quantum lower bounds by polynomials".
4110:
3860:. This relationship is optimal up to polylogarithmic factors. As for quantum decision tree complexities,
1139:
are a generalization of linear decision trees that allow the test functions to be polynomials of degree
899:
5111:
4931:
4495:
2061:
1317:
521:
4435:
2875:
2472:
2142:
1878:
1604:
1462:
1162:
These decision tree models, defined by Rabin and
Reingold, are often used for proving lower bounds in
814:
comparisons to find the minimum. (The information-theoretic argument here only gives a lower bound of
4925:
421:
381:
301:
4560:
2057:
726:
53:
that are done adaptively, so the outcome of previous tests can influence the tests performed next.
5788:
4008:
2187:
1277:
1159:. Geometrically, the space is divided into semi-algebraic sets (a generalization of hyperplane).
1072:
341:
5650:
Huang, Hao (2019). "Induced subgraphs of hypercubes and a proof of the
Sensitivity Conjecture".
2831:
2253:
2110:
1163:
488:
4047:
3092:
3002:
2716:
2680:
2640:
2604:
2518:
2378:
2014:
1972:
1926:
1784:
113:
2779:
1961:
817:
3147:
3057:
2227:
201:
175:
5689:
4868:
4821:
4631:
2337:
1756:
1507:
1361:
1045:
1018:
148:
38:
4895:
4384:
4320:
4083:
2555:
2552:, is defined as the depth of the lowest-depth quantum decision tree that gives the result
2415:
2056:
The nondeterministic decision tree complexity of a function is known more commonly as the
1821:
1818:
is defined as the complexity of the lowest-depth randomized decision tree whose result is
1670:
1575:
1534:
1358:. This was first showed for linear decision models by Dobkin and Lipton. They also show a
1222:
468:
8:
4122:
2752:
These notions are typically bounded by the notions of degree and approximate degree. The
2444:
1965:
1850:
1251:
1130:
791:
80:
57:
5610:
Midrijanis, Gatis (2004), "Exact quantum query complexity for total
Boolean functions",
5333:
608:
585:
5741:
5693:
5685:
5659:
5631:
5611:
5590:
5571:
5545:
5481:
5401:
5383:
5275:
5197:
5105:
4848:
4743:
4723:
4703:
4683:
4663:
4611:
4415:
4357:
4300:
4280:
4260:
4240:
4220:
4200:
3343:
3323:
2982:
2924:
2811:
2759:
2584:
2317:
2297:
2090:
2070:
1724:
1704:
1649:
1142:
1112:
771:
720:
565:
93:
5761:
5143:
5126:
5697:
5677:
5563:
5353:
5349:
5314:
5265:
5232:
5222:
5189:
5148:
5093:
5083:
5056:
5575:
5485:
5254:. STOC '83. New York, NY, USA: Association for Computing Machinery. pp. 80–86.
5201:
5756:
5669:
5555:
5473:
5405:
5393:
5345:
5306:
5279:
5255:
5252:
Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83
5179:
5138:
5052:
5048:
4128:
1394:
5036:
5000:
3761:.) A tighter relationship is known between the Monte Carlo and Las Vegas models:
847:
236:
87:
5673:
4002:
3997:
It is important to note that these polynomial relationships are valid only for
5250:
Ben-Or, Michael (1983-12-01). "Lower bounds for algebraic computation trees".
3476:{\displaystyle Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n}
5772:
5681:
5567:
5357:
5318:
5294:
5193:
5152:
5097:
5060:
5005:
3315:
2412:
is the depth of the lowest-depth quantum decision tree that gives the result
42:
5236:
1166:. For example, Ben-Or showed that element uniqueness (the task of computing
859:
5630:
Midrijanis, Gatis (2005), "On
Randomized and Quantum Query Complexities",
5397:
5260:
5184:
5077:
1721:
is the smallest depth among all deterministic decision trees that compute
5636:
5616:
5448:
Tardos, G. (1989). "Query complexity, or why is it difficult to separate
5388:
5216:
5082:. Cormen, Thomas H. (Third ed.). Cambridge, Mass.: MIT Press. 2009.
1753:
is to add additional nodes to the tree, each controlled by a probability
1393:
For
Boolean decision trees, the task is to compute the value of an n-bit
463:
72:
5419:
Blum, M.; Impagliazzo, R. (1987). "Generic oracles and oracle classes".
5167:
2064:
would need to look at in order to evaluate the function with certainty.
1109:. From its definition, linear decision trees can only specify functions
145:
comparisons. For comparison sorts, a query is a comparison of two items
5502:
5477:
3624:
1133:
can be constructed by taking unions and intersections of half-spaces.
239:, which means that they only gain information about an input sequence
21:
708:
5559:
5310:
5664:
5595:
5550:
4346:. Sensitivity is related to the notion of total influence from the
4109:
is possible; the first example of such a problem was discovered by
846:.) A similar argument works for general lower bounds for computing
712:
5533:
5373:
56:
Typically, these tests have a small number of outcomes (such as a
227:
2060:
of that function. It measures the number of input bits that a
5713:"Decades-Old Computer Science Conjecture Solved in Two Pages"
86:
For example, a decision tree argument is used to show that a
5742:"Complexity Measures and Decision Tree Complexity: A Survey"
5534:"Separations in Query Complexity Based on Pointer Functions"
5588:
3316:
Relationships between boolean function complexity measures
1008:{\displaystyle a_{0}+\textstyle \sum _{i=1}^{n}a_{i}x_{i}}
172:, with two outcomes (assuming no items are equal): either
3320:
It follows immediately from the definitions that for all
5531:
1504:. The queries correspond to reading a bit of the input,
71:
Decision trees models are instrumental in establishing
5035:
Ford, Lester R. Jr.; Johnson, Selmer M. (1959-05-01).
3305:{\displaystyle Q_{2}(f)\geq {\widetilde {\deg }}(f)/2}
962:
853:
41:
in which an algorithm is considered to be basically a
4934:
4898:
4871:
4851:
4824:
4766:
4746:
4726:
4706:
4686:
4666:
4634:
4614:
4563:
4498:
4438:
4418:
4387:
4360:
4323:
4303:
4283:
4263:
4243:
4223:
4203:
4136:
4086:
4050:
4011:
3933:
3866:
3853:{\displaystyle R_{0}(f)=O(R_{2}(f)^{2}\log R_{2}(f))}
3767:
3700:
3633:
3571:
3489:
3366:
3346:
3326:
3250:
3188:
3150:
3095:
3060:
3005:
2985:
2947:
2927:
2878:
2834:
2814:
2782:
2762:
2719:
2683:
2643:
2607:
2587:
2558:
2521:
2475:
2447:
2418:
2381:
2340:
2320:
2300:
2256:
2230:
2190:
2145:
2113:
2093:
2073:
2017:
1975:
1929:
1881:
1853:
1824:
1787:
1759:
1727:
1707:
1673:
1652:
1607:
1578:
1537:
1510:
1465:
1402:
1388:
1364:
1320:
1280:
1254:
1248:
is 0 if and only if there exist distinct coordinates
1225:
1172:
1145:
1115:
1075:
1048:
1021:
948:
902:
867:
820:
794:
774:
729:
723:
that a correct sorting algorithm must learn at least
634:
611:
588:
568:
524:
491:
471:
424:
384:
344:
304:
245:
204:
178:
151:
116:
96:
83:
and type of query algorithms are allowed to perform.
5433:
5427:
5412:
4660:, is defined to be the maximum block sensitivity of
3555:{\displaystyle Q_{2}(f)\leq Q_{0}(f)\leq D(f)\leq n}
700:{\displaystyle \log _{2}(n!)=\Omega (n\log _{2}(n))}
5418:
5221:. Shamos, Michael Ian. New York: Springer-Verlag.
4983:
4913:
4884:
4857:
4837:
4810:
4752:
4732:
4712:
4692:
4672:
4652:
4620:
4593:
4549:
4484:
4424:
4404:
4366:
4338:
4309:
4289:
4269:
4249:
4229:
4209:
4185:
4101:
4072:
4036:
3986:
3927:, and this bound is tight. Midrijanis showed that
3919:
3852:
3753:
3686:
3615:
3554:
3475:
3352:
3332:
3304:
3236:
3171:
3136:
3081:
3046:
2991:
2971:
2933:
2909:
2864:
2820:
2800:
2768:
2741:
2705:
2665:
2629:
2593:
2573:
2543:
2506:
2461:
2433:
2403:
2358:
2326:
2306:
2286:
2242:
2216:
2176:
2131:
2099:
2079:
2039:
1997:
1951:
1912:
1867:
1839:
1809:
1772:
1733:
1713:
1688:
1658:
1638:
1593:
1552:
1523:
1496:
1451:
1377:
1350:
1306:
1266:
1240:
1211:
1151:
1121:
1101:
1061:
1034:
1007:
934:
888:
838:
806:
780:
757:
699:
620:
597:
574:
554:
507:
477:
450:
410:
370:
330:
290:
216:
190:
164:
137:
102:
5436:Technical Report DCS TR86-796, Cornell University
5331:
5127:"Proving simultaneous positivity of linear forms"
2051:
5770:
5293:Dobkin, David; Lipton, Richard J. (1976-06-01).
4928:proved the sensitivity conjecture, showing that
3994:, improving a quartic bound due to Beals et al.
5332:Michael Steele, J; Yao, Andrew C (1982-03-01).
2581:with probability 1 in all cases (i.e. computes
2314:is the maximum certificate complexity over all
1314:) requires an algebraic decision tree of depth
5739:
4557:. One can show through a simple argument that
2107:is the size of the smallest subset of indices
1567:
5218:Computational geometry : an introduction
1212:{\displaystyle f:\mathbb {R} ^{n}\to \{0,1\}}
228:Comparison trees and lower bounds for sorting
5292:
4217:is defined to be the maximum sensitivity of
4180:
4168:
4156:
4143:
4025:
4012:
2898:
2885:
2495:
2482:
2165:
2152:
1901:
1888:
1627:
1614:
1485:
1472:
1446:
1434:
1422:
1409:
1206:
1194:
518:One can show that comparison sorts must use
5623:
5527:
5525:
5334:"Lower bounds for algebraic decision trees"
5034:
5016:Minimum spanning tree § Decision trees
4811:{\displaystyle S_{1},\ldots ,S_{t}\subset }
2979:, is the smallest degree of any polynomial
2808:, is the smallest degree of any polynomial
1744:
5629:
5609:
5603:
5168:"On the Optimality of Some Set Algorithms"
5760:
5663:
5635:
5615:
5594:
5549:
5505:(1989). "CREW PRAMs and decision trees".
5387:
5259:
5214:
5183:
5142:
4116:
1646:, the decision tree is said to "compute"
1181:
876:
291:{\displaystyle x_{1},x_{2},\ldots ,x_{n}}
235:For example, many sorting algorithms are
158:
5740:Buhrman, Harry; de Wolf, Ronald (2002),
5522:
5497:
5495:
5165:
4186:{\displaystyle f:\{0,1\}^{n}\to \{0,1\}}
2369:
2067:Formally, the certificate complexity of
1452:{\displaystyle f:\{0,1\}^{n}\to \{0,1\}}
715:, demonstrates that the bound is tight.
20:
5369:
5367:
5131:Journal of Computer and System Sciences
4297:is the number of single-bit changes in
2972:{\displaystyle {\widetilde {\deg }}(f)}
298:via local comparisons: testing whether
5771:
5447:
5441:
5249:
5072:
5070:
3237:{\displaystyle Q_{0}(f)\geq \deg(f)/2}
605:leaves. Any binary tree with at least
5710:
5649:
5643:
5582:
5501:
5492:
5295:"Multidimensional Searching Problems"
5124:
3616:{\displaystyle D(f)\leq R_{0}(f)^{2}}
2374:The quantum decision tree complexity
889:{\displaystyle x\in \mathbb {R} ^{n}}
5513:
5364:
4044:, an exponential separation between
3987:{\displaystyle D(f)=O(Q_{0}(f)^{3})}
3920:{\displaystyle D(f)=O(Q_{2}(f)^{4})}
3754:{\displaystyle D(f)=O(R_{1}(f)^{2})}
3687:{\displaystyle D(f)=O(R_{2}(f)^{3})}
1920:(i.e., with bounded 2-sided error).
1572:If the output of a decision tree is
5067:
1069:corresponds to the linear function
854:Linear and algebraic decision trees
13:
5166:Reingold, Edward M. (1972-10-01).
5011:Aanderaa–Karp–Rosenberg conjecture
4818:such that, for any of the subsets
1389:Boolean decision tree complexities
1321:
935:{\displaystyle a_{0},\dots ,a_{n}}
663:
525:
14:
5800:
5041:The American Mathematical Monthly
4984:{\displaystyle bs(f)=O(s(f)^{4})}
4550:{\displaystyle s(f)=O(D(f)^{c'})}
4005:, that have a domain a subset of
1351:{\displaystyle \Omega (n\log(n))}
555:{\displaystyle \Omega (n\log(n))}
515:, re-orders the input sequence.)
16:Model of computational complexity
5125:Rabin, Michael O. (1972-12-01).
4485:{\displaystyle D(f)=O(s(f)^{c})}
2910:{\displaystyle x\in \{0,1\}^{n}}
2507:{\displaystyle x\in \{0,1\}^{n}}
2294:. The certificate complexity of
2177:{\displaystyle y\in \{0,1\}^{n}}
1913:{\displaystyle x\in \{0,1\}^{n}}
1639:{\displaystyle x\in \{0,1\}^{n}}
1497:{\displaystyle x\in \{0,1\}^{n}}
5779:Computational complexity theory
5704:
5325:
5286:
5243:
5208:
5159:
5118:
5053:10.1080/00029890.1959.11989306
5028:
4978:
4969:
4962:
4956:
4947:
4941:
4908:
4902:
4805:
4799:
4647:
4641:
4588:
4582:
4573:
4567:
4544:
4530:
4523:
4517:
4508:
4502:
4479:
4470:
4463:
4457:
4448:
4442:
4333:
4327:
4165:
4096:
4090:
4067:
4061:
3981:
3972:
3965:
3952:
3943:
3937:
3914:
3905:
3898:
3885:
3876:
3870:
3847:
3844:
3838:
3813:
3806:
3793:
3784:
3778:
3748:
3739:
3732:
3719:
3710:
3704:
3681:
3672:
3665:
3652:
3643:
3637:
3604:
3597:
3581:
3575:
3543:
3537:
3528:
3522:
3506:
3500:
3464:
3458:
3449:
3443:
3427:
3421:
3405:
3399:
3383:
3377:
3291:
3285:
3267:
3261:
3223:
3217:
3205:
3199:
3182:Beals et al. established that
3160:
3154:
3131:
3111:
3105:
3099:
3070:
3064:
3041:
3021:
3015:
3009:
2966:
2960:
2859:
2853:
2844:
2838:
2795:
2789:
2736:
2730:
2700:
2694:
2660:
2654:
2624:
2618:
2568:
2562:
2538:
2532:
2428:
2422:
2398:
2392:
2353:
2347:
2281:
2275:
2266:
2260:
2126:
2120:
2052:Nondeterministic decision tree
2034:
2028:
1992:
1986:
1946:
1940:
1834:
1828:
1804:
1798:
1683:
1677:
1588:
1582:
1547:
1541:
1431:
1345:
1342:
1336:
1324:
1235:
1229:
1191:
833:
827:
752:
743:
721:information-theoretic argument
694:
691:
685:
666:
657:
648:
549:
546:
540:
528:
451:{\displaystyle x_{i}>x_{j}}
411:{\displaystyle x_{i}>x_{j}}
331:{\displaystyle x_{i}<x_{j}}
132:
126:
1:
5762:10.1016/S0304-3975(01)00144-X
5421:Proceedings of 18th IEEE FOCS
5215:Preparata, Franco P. (1985).
5144:10.1016/S0022-0000(72)80034-5
5021:
4594:{\displaystyle s(f)\leq D(f)}
4348:analysis of Boolean functions
758:{\displaystyle \log _{2}(n!)}
5749:Theoretical Computer Science
5507:Proceedings of 21st ACM STOC
5350:10.1016/0196-6774(82)90002-5
7:
5690:10.4007/annals.2019.190.3.6
5674:10.4007/annals.2019.190.3.6
4994:
4700:. The block sensitivity of
4257:, where the sensitivity of
4037:{\displaystyle \{0,1\}^{n}}
3694:. (Nisan also showed that
2673:are more commonly known as
2217:{\displaystyle y_{i}=x_{i}}
1699:deterministic decision tree
1568:Deterministic decision tree
1307:{\displaystyle x_{i}=x_{j}}
1102:{\displaystyle x_{i}-x_{j}}
371:{\displaystyle x_{i}=x_{j}}
10:
5805:
5733:
5079:Introduction to algorithms
4120:
2675:quantum query complexities
2441:with probability at least
2062:nondeterministic algorithm
1847:with probability at least
628:leaves has depth at least
5299:SIAM Journal on Computing
4317:that change the value of
4003:partial Boolean functions
2865:{\displaystyle f(x)=p(x)}
2287:{\displaystyle f(y)=f(x)}
2132:{\displaystyle S\subset }
1968:decision-tree complexity
508:{\displaystyle \pi ^{-1}}
4073:{\displaystyle Q_{0}(f)}
4001:Boolean functions. For
3137:{\displaystyle p(x)\in }
3047:{\displaystyle p(x)\in }
2742:{\displaystyle Q_{1}(f)}
2706:{\displaystyle Q_{0}(f)}
2666:{\displaystyle Q_{E}(f)}
2630:{\displaystyle Q_{2}(f)}
2544:{\displaystyle Q_{E}(f)}
2404:{\displaystyle Q_{2}(f)}
2040:{\displaystyle R_{1}(f)}
1998:{\displaystyle R_{0}(f)}
1952:{\displaystyle R_{2}(f)}
1810:{\displaystyle R_{2}(f)}
1751:randomized decision tree
1745:Randomized decision tree
1137:Algebraic decision trees
138:{\displaystyle n\log(n)}
62:decision tree complexity
31:computational complexity
4845:, flipping the bits of
3340:-bit Boolean functions
2801:{\displaystyle \deg(f)}
839:{\displaystyle \log(n)}
5110:: CS1 maint: others (
5037:"A Tournament Problem"
4985:
4915:
4886:
4859:
4839:
4812:
4754:
4740:is the maximum number
4734:
4714:
4694:
4674:
4654:
4622:
4595:
4551:
4486:
4426:
4406:
4379:sensitivity conjecture
4368:
4340:
4311:
4291:
4271:
4251:
4231:
4211:
4187:
4117:Sensitivity conjecture
4103:
4074:
4038:
3988:
3921:
3854:
3755:
3688:
3617:
3556:
3477:
3354:
3334:
3306:
3238:
3173:
3172:{\displaystyle f(x)=1}
3138:
3083:
3082:{\displaystyle f(x)=0}
3048:
2993:
2973:
2935:
2911:
2866:
2822:
2802:
2770:
2743:
2707:
2667:
2631:
2595:
2575:
2545:
2508:
2463:
2435:
2405:
2360:
2328:
2308:
2288:
2244:
2243:{\displaystyle i\in S}
2218:
2178:
2133:
2101:
2081:
2058:certificate complexity
2041:
1999:
1953:
1914:
1869:
1841:
1811:
1774:
1735:
1715:
1690:
1660:
1640:
1595:
1554:
1525:
1498:
1453:
1379:
1352:
1308:
1268:
1242:
1213:
1164:computational geometry
1153:
1123:
1103:
1063:
1036:
1009:
983:
936:
890:
840:
808:
782:
759:
701:
622:
599:
576:
556:
509:
479:
452:
412:
372:
332:
292:
218:
217:{\displaystyle a>b}
192:
191:{\displaystyle a<b}
166:
139:
104:
45:, i.e., a sequence of
26:
5784:Models of computation
5652:Annals of Mathematics
5398:10.1145/502090.502097
5338:Journal of Algorithms
5261:10.1145/800061.808735
5185:10.1145/321724.321730
4986:
4916:
4892:changes the value of
4887:
4885:{\displaystyle S_{i}}
4860:
4840:
4838:{\displaystyle S_{i}}
4813:
4755:
4735:
4715:
4695:
4675:
4655:
4653:{\displaystyle bs(f)}
4623:
4596:
4552:
4487:
4427:
4407:
4369:
4354:sensitivity over all
4341:
4312:
4292:
4272:
4252:
4232:
4212:
4188:
4104:
4075:
4039:
3989:
3922:
3855:
3756:
3689:
3618:
3557:
3478:
3355:
3335:
3307:
3239:
3174:
3139:
3084:
3049:
2994:
2974:
2936:
2912:
2867:
2823:
2803:
2771:
2744:
2708:
2668:
2632:
2596:
2576:
2546:
2514:. Another quantity,
2509:
2464:
2436:
2406:
2370:Quantum decision tree
2361:
2359:{\displaystyle RC(f)}
2329:
2309:
2289:
2245:
2219:
2179:
2134:
2102:
2082:
2042:
2000:
1954:
1915:
1870:
1842:
1812:
1775:
1773:{\displaystyle p_{i}}
1736:
1716:
1691:
1661:
1641:
1596:
1555:
1526:
1524:{\displaystyle x_{i}}
1499:
1454:
1380:
1378:{\displaystyle n^{2}}
1353:
1309:
1269:
1243:
1214:
1154:
1124:
1104:
1064:
1062:{\displaystyle x_{j}}
1037:
1035:{\displaystyle x_{i}}
1010:
963:
942:, output the sign of
937:
891:
841:
809:
783:
760:
702:
623:
600:
577:
557:
510:
480:
453:
413:
373:
333:
293:
219:
193:
167:
165:{\displaystyle a,\,b}
140:
105:
24:
4932:
4914:{\displaystyle f(x)}
4896:
4869:
4849:
4822:
4764:
4760:of disjoint subsets
4744:
4724:
4704:
4684:
4664:
4632:
4612:
4561:
4496:
4436:
4416:
4405:{\displaystyle c,c'}
4385:
4358:
4350:, which is equal to
4339:{\displaystyle f(x)}
4321:
4301:
4281:
4261:
4241:
4221:
4201:
4134:
4102:{\displaystyle D(f)}
4084:
4048:
4009:
3931:
3864:
3765:
3698:
3631:
3569:
3487:
3364:
3344:
3324:
3248:
3186:
3148:
3093:
3058:
3003:
2983:
2945:
2925:
2876:
2832:
2812:
2780:
2760:
2717:
2681:
2641:
2605:
2585:
2574:{\displaystyle f(x)}
2556:
2519:
2473:
2445:
2434:{\displaystyle f(x)}
2416:
2379:
2338:
2318:
2298:
2254:
2228:
2188:
2143:
2111:
2091:
2071:
2015:
1973:
1927:
1879:
1851:
1840:{\displaystyle f(x)}
1822:
1785:
1757:
1749:One way to define a
1725:
1705:
1689:{\displaystyle D(f)}
1671:
1650:
1605:
1594:{\displaystyle f(x)}
1576:
1553:{\displaystyle f(x)}
1535:
1531:, and the output is
1508:
1463:
1400:
1362:
1318:
1278:
1252:
1241:{\displaystyle f(x)}
1223:
1170:
1143:
1113:
1073:
1046:
1019:
946:
900:
865:
818:
792:
772:
727:
632:
609:
586:
566:
522:
489:
478:{\displaystyle \pi }
469:
422:
382:
342:
302:
243:
202:
176:
149:
114:
94:
39:model of computation
5509:. pp. 327–335.
5423:. pp. 118–126.
4412:such that, for all
4123:Sensitivity theorem
2462:{\displaystyle 2/3}
2139:such that, for all
1868:{\displaystyle 2/3}
1562:complexity measures
1267:{\displaystyle i,j}
807:{\displaystyle n-1}
81:computational model
35:decision tree model
25:Decision Tree Model
5711:Klarreich, Erica.
5538:Journal of the ACM
5478:10.1007/BF02125350
5460:by random oracles
5376:Journal of the ACM
5172:Journal of the ACM
4981:
4911:
4882:
4855:
4835:
4808:
4750:
4730:
4710:
4690:
4670:
4650:
4618:
4591:
4547:
4482:
4422:
4402:
4364:
4336:
4307:
4287:
4267:
4247:
4227:
4207:
4183:
4099:
4070:
4034:
3984:
3917:
3850:
3751:
3684:
3613:
3552:
3473:
3350:
3330:
3302:
3234:
3169:
3134:
3079:
3044:
2989:
2969:
2931:
2919:approximate degree
2907:
2862:
2818:
2798:
2766:
2739:
2703:
2663:
2627:
2591:
2571:
2541:
2504:
2459:
2431:
2401:
2356:
2324:
2304:
2284:
2240:
2214:
2174:
2129:
2097:
2077:
2037:
1995:
1949:
1910:
1865:
1837:
1807:
1770:
1731:
1711:
1686:
1656:
1636:
1591:
1550:
1521:
1494:
1449:
1375:
1348:
1304:
1264:
1238:
1209:
1149:
1119:
1099:
1059:
1032:
1005:
1004:
932:
886:
836:
804:
778:
755:
697:
621:{\displaystyle n!}
618:
598:{\displaystyle n!}
595:
572:
552:
505:
475:
448:
408:
368:
328:
288:
214:
188:
162:
135:
100:
27:
5544:(5): 32:1–32:24.
5271:978-0-89791-099-6
5089:978-0-262-27083-0
4865:corresponding to
4858:{\displaystyle x}
4753:{\displaystyle t}
4733:{\displaystyle x}
4713:{\displaystyle f}
4693:{\displaystyle x}
4673:{\displaystyle f}
4621:{\displaystyle f}
4606:block sensitivity
4425:{\displaystyle f}
4367:{\displaystyle x}
4310:{\displaystyle x}
4290:{\displaystyle x}
4270:{\displaystyle f}
4250:{\displaystyle x}
4230:{\displaystyle f}
4210:{\displaystyle f}
4111:Deutsch and Jozsa
3353:{\displaystyle f}
3333:{\displaystyle n}
3282:
2992:{\displaystyle p}
2957:
2934:{\displaystyle f}
2821:{\displaystyle p}
2769:{\displaystyle f}
2594:{\displaystyle f}
2327:{\displaystyle x}
2307:{\displaystyle f}
2100:{\displaystyle x}
2080:{\displaystyle f}
1734:{\displaystyle f}
1714:{\displaystyle f}
1659:{\displaystyle f}
1152:{\displaystyle d}
1122:{\displaystyle f}
781:{\displaystyle n}
575:{\displaystyle n}
103:{\displaystyle n}
77:complexity theory
5796:
5765:
5764:
5746:
5727:
5726:
5724:
5723:
5708:
5702:
5701:
5667:
5647:
5641:
5640:
5639:
5637:quant-ph/0501142
5627:
5621:
5620:
5619:
5617:quant-ph/0403168
5607:
5601:
5600:
5598:
5586:
5580:
5579:
5553:
5529:
5520:
5517:
5511:
5510:
5499:
5490:
5489:
5445:
5439:
5438:
5431:
5425:
5424:
5416:
5410:
5409:
5391:
5389:quant-ph/9802049
5371:
5362:
5361:
5329:
5323:
5322:
5290:
5284:
5283:
5263:
5247:
5241:
5240:
5212:
5206:
5205:
5187:
5163:
5157:
5156:
5146:
5122:
5116:
5115:
5109:
5101:
5074:
5065:
5064:
5032:
4990:
4988:
4987:
4982:
4977:
4976:
4920:
4918:
4917:
4912:
4891:
4889:
4888:
4883:
4881:
4880:
4864:
4862:
4861:
4856:
4844:
4842:
4841:
4836:
4834:
4833:
4817:
4815:
4814:
4809:
4795:
4794:
4776:
4775:
4759:
4757:
4756:
4751:
4739:
4737:
4736:
4731:
4719:
4717:
4716:
4711:
4699:
4697:
4696:
4691:
4679:
4677:
4676:
4671:
4659:
4657:
4656:
4651:
4627:
4625:
4624:
4619:
4600:
4598:
4597:
4592:
4556:
4554:
4553:
4548:
4543:
4542:
4541:
4491:
4489:
4488:
4483:
4478:
4477:
4431:
4429:
4428:
4423:
4411:
4409:
4408:
4403:
4401:
4373:
4371:
4370:
4365:
4345:
4343:
4342:
4337:
4316:
4314:
4313:
4308:
4296:
4294:
4293:
4288:
4276:
4274:
4273:
4268:
4256:
4254:
4253:
4248:
4236:
4234:
4233:
4228:
4216:
4214:
4213:
4208:
4192:
4190:
4189:
4184:
4164:
4163:
4129:Boolean function
4108:
4106:
4105:
4100:
4079:
4077:
4076:
4071:
4060:
4059:
4043:
4041:
4040:
4035:
4033:
4032:
3993:
3991:
3990:
3985:
3980:
3979:
3964:
3963:
3926:
3924:
3923:
3918:
3913:
3912:
3897:
3896:
3859:
3857:
3856:
3851:
3837:
3836:
3821:
3820:
3805:
3804:
3777:
3776:
3760:
3758:
3757:
3752:
3747:
3746:
3731:
3730:
3693:
3691:
3690:
3685:
3680:
3679:
3664:
3663:
3622:
3620:
3619:
3614:
3612:
3611:
3596:
3595:
3561:
3559:
3558:
3553:
3521:
3520:
3499:
3498:
3482:
3480:
3479:
3474:
3442:
3441:
3420:
3419:
3398:
3397:
3376:
3375:
3359:
3357:
3356:
3351:
3339:
3337:
3336:
3331:
3311:
3309:
3308:
3303:
3298:
3284:
3283:
3275:
3260:
3259:
3243:
3241:
3240:
3235:
3230:
3198:
3197:
3178:
3176:
3175:
3170:
3143:
3141:
3140:
3135:
3121:
3088:
3086:
3085:
3080:
3053:
3051:
3050:
3045:
3037:
2998:
2996:
2995:
2990:
2978:
2976:
2975:
2970:
2959:
2958:
2950:
2940:
2938:
2937:
2932:
2916:
2914:
2913:
2908:
2906:
2905:
2871:
2869:
2868:
2863:
2827:
2825:
2824:
2819:
2807:
2805:
2804:
2799:
2775:
2773:
2772:
2767:
2748:
2746:
2745:
2740:
2729:
2728:
2712:
2710:
2709:
2704:
2693:
2692:
2672:
2670:
2669:
2664:
2653:
2652:
2636:
2634:
2633:
2628:
2617:
2616:
2600:
2598:
2597:
2592:
2580:
2578:
2577:
2572:
2550:
2548:
2547:
2542:
2531:
2530:
2513:
2511:
2510:
2505:
2503:
2502:
2468:
2466:
2465:
2460:
2455:
2440:
2438:
2437:
2432:
2410:
2408:
2407:
2402:
2391:
2390:
2365:
2363:
2362:
2357:
2333:
2331:
2330:
2325:
2313:
2311:
2310:
2305:
2293:
2291:
2290:
2285:
2249:
2247:
2246:
2241:
2223:
2221:
2220:
2215:
2213:
2212:
2200:
2199:
2183:
2181:
2180:
2175:
2173:
2172:
2138:
2136:
2135:
2130:
2106:
2104:
2103:
2098:
2086:
2084:
2083:
2078:
2046:
2044:
2043:
2038:
2027:
2026:
2004:
2002:
2001:
1996:
1985:
1984:
1960:is known as the
1958:
1956:
1955:
1950:
1939:
1938:
1919:
1917:
1916:
1911:
1909:
1908:
1874:
1872:
1871:
1866:
1861:
1846:
1844:
1843:
1838:
1816:
1814:
1813:
1808:
1797:
1796:
1779:
1777:
1776:
1771:
1769:
1768:
1740:
1738:
1737:
1732:
1720:
1718:
1717:
1712:
1695:
1693:
1692:
1687:
1665:
1663:
1662:
1657:
1645:
1643:
1642:
1637:
1635:
1634:
1600:
1598:
1597:
1592:
1559:
1557:
1556:
1551:
1530:
1528:
1527:
1522:
1520:
1519:
1503:
1501:
1500:
1495:
1493:
1492:
1458:
1456:
1455:
1450:
1430:
1429:
1395:Boolean function
1384:
1382:
1381:
1376:
1374:
1373:
1357:
1355:
1354:
1349:
1313:
1311:
1310:
1305:
1303:
1302:
1290:
1289:
1273:
1271:
1270:
1265:
1247:
1245:
1244:
1239:
1218:
1216:
1215:
1210:
1190:
1189:
1184:
1158:
1156:
1155:
1150:
1128:
1126:
1125:
1120:
1108:
1106:
1105:
1100:
1098:
1097:
1085:
1084:
1068:
1066:
1065:
1060:
1058:
1057:
1041:
1039:
1038:
1033:
1031:
1030:
1014:
1012:
1011:
1006:
1003:
1002:
993:
992:
982:
977:
958:
957:
941:
939:
938:
933:
931:
930:
912:
911:
895:
893:
892:
887:
885:
884:
879:
848:order statistics
845:
843:
842:
837:
813:
811:
810:
805:
787:
785:
784:
779:
764:
762:
761:
756:
739:
738:
706:
704:
703:
698:
681:
680:
644:
643:
627:
625:
624:
619:
604:
602:
601:
596:
581:
579:
578:
573:
561:
559:
558:
553:
514:
512:
511:
506:
504:
503:
484:
482:
481:
476:
457:
455:
454:
449:
447:
446:
434:
433:
417:
415:
414:
409:
407:
406:
394:
393:
377:
375:
374:
369:
367:
366:
354:
353:
337:
335:
334:
329:
327:
326:
314:
313:
297:
295:
294:
289:
287:
286:
268:
267:
255:
254:
237:comparison sorts
223:
221:
220:
215:
197:
195:
194:
189:
171:
169:
168:
163:
144:
142:
141:
136:
110:items must take
109:
107:
106:
101:
66:query complexity
5804:
5803:
5799:
5798:
5797:
5795:
5794:
5793:
5769:
5768:
5744:
5736:
5731:
5730:
5721:
5719:
5717:Quanta Magazine
5709:
5705:
5648:
5644:
5628:
5624:
5608:
5604:
5587:
5583:
5560:10.1145/3106234
5530:
5523:
5518:
5514:
5500:
5493:
5446:
5442:
5432:
5428:
5417:
5413:
5372:
5365:
5330:
5326:
5311:10.1137/0205015
5291:
5287:
5272:
5248:
5244:
5229:
5213:
5209:
5164:
5160:
5123:
5119:
5103:
5102:
5090:
5076:
5075:
5068:
5033:
5029:
5024:
5001:Comparison sort
4997:
4972:
4968:
4933:
4930:
4929:
4897:
4894:
4893:
4876:
4872:
4870:
4867:
4866:
4850:
4847:
4846:
4829:
4825:
4823:
4820:
4819:
4790:
4786:
4771:
4767:
4765:
4762:
4761:
4745:
4742:
4741:
4725:
4722:
4721:
4705:
4702:
4701:
4685:
4682:
4681:
4665:
4662:
4661:
4633:
4630:
4629:
4613:
4610:
4609:
4562:
4559:
4558:
4534:
4533:
4529:
4497:
4494:
4493:
4473:
4469:
4437:
4434:
4433:
4417:
4414:
4413:
4394:
4386:
4383:
4382:
4359:
4356:
4355:
4322:
4319:
4318:
4302:
4299:
4298:
4282:
4279:
4278:
4262:
4259:
4258:
4242:
4239:
4238:
4222:
4219:
4218:
4202:
4199:
4198:
4159:
4155:
4135:
4132:
4131:
4125:
4119:
4085:
4082:
4081:
4055:
4051:
4049:
4046:
4045:
4028:
4024:
4010:
4007:
4006:
3975:
3971:
3959:
3955:
3932:
3929:
3928:
3908:
3904:
3892:
3888:
3865:
3862:
3861:
3832:
3828:
3816:
3812:
3800:
3796:
3772:
3768:
3766:
3763:
3762:
3742:
3738:
3726:
3722:
3699:
3696:
3695:
3675:
3671:
3659:
3655:
3632:
3629:
3628:
3607:
3603:
3591:
3587:
3570:
3567:
3566:
3516:
3512:
3494:
3490:
3488:
3485:
3484:
3437:
3433:
3415:
3411:
3393:
3389:
3371:
3367:
3365:
3362:
3361:
3345:
3342:
3341:
3325:
3322:
3321:
3318:
3294:
3274:
3273:
3255:
3251:
3249:
3246:
3245:
3226:
3193:
3189:
3187:
3184:
3183:
3149:
3146:
3145:
3117:
3094:
3091:
3090:
3059:
3056:
3055:
3033:
3004:
3001:
3000:
2984:
2981:
2980:
2949:
2948:
2946:
2943:
2942:
2926:
2923:
2922:
2901:
2897:
2877:
2874:
2873:
2833:
2830:
2829:
2813:
2810:
2809:
2781:
2778:
2777:
2761:
2758:
2757:
2724:
2720:
2718:
2715:
2714:
2688:
2684:
2682:
2679:
2678:
2648:
2644:
2642:
2639:
2638:
2612:
2608:
2606:
2603:
2602:
2586:
2583:
2582:
2557:
2554:
2553:
2526:
2522:
2520:
2517:
2516:
2498:
2494:
2474:
2471:
2470:
2451:
2446:
2443:
2442:
2417:
2414:
2413:
2386:
2382:
2380:
2377:
2376:
2372:
2339:
2336:
2335:
2319:
2316:
2315:
2299:
2296:
2295:
2255:
2252:
2251:
2229:
2226:
2225:
2208:
2204:
2195:
2191:
2189:
2186:
2185:
2168:
2164:
2144:
2141:
2140:
2112:
2109:
2108:
2092:
2089:
2088:
2072:
2069:
2068:
2054:
2022:
2018:
2016:
2013:
2012:
1980:
1976:
1974:
1971:
1970:
1934:
1930:
1928:
1925:
1924:
1904:
1900:
1880:
1877:
1876:
1857:
1852:
1849:
1848:
1823:
1820:
1819:
1792:
1788:
1786:
1783:
1782:
1764:
1760:
1758:
1755:
1754:
1747:
1726:
1723:
1722:
1706:
1703:
1702:
1672:
1669:
1668:
1651:
1648:
1647:
1630:
1626:
1606:
1603:
1602:
1577:
1574:
1573:
1570:
1536:
1533:
1532:
1515:
1511:
1509:
1506:
1505:
1488:
1484:
1464:
1461:
1460:
1425:
1421:
1401:
1398:
1397:
1391:
1369:
1365:
1363:
1360:
1359:
1319:
1316:
1315:
1298:
1294:
1285:
1281:
1279:
1276:
1275:
1253:
1250:
1249:
1224:
1221:
1220:
1185:
1180:
1179:
1171:
1168:
1167:
1144:
1141:
1140:
1114:
1111:
1110:
1093:
1089:
1080:
1076:
1074:
1071:
1070:
1053:
1049:
1047:
1044:
1043:
1026:
1022:
1020:
1017:
1016:
998:
994:
988:
984:
978:
967:
953:
949:
947:
944:
943:
926:
922:
907:
903:
901:
898:
897:
880:
875:
874:
866:
863:
862:
856:
819:
816:
815:
793:
790:
789:
773:
770:
769:
734:
730:
728:
725:
724:
676:
672:
639:
635:
633:
630:
629:
610:
607:
606:
587:
584:
583:
567:
564:
563:
523:
520:
519:
496:
492:
490:
487:
486:
470:
467:
466:
442:
438:
429:
425:
423:
420:
419:
402:
398:
389:
385:
383:
380:
379:
362:
358:
349:
345:
343:
340:
339:
322:
318:
309:
305:
303:
300:
299:
282:
278:
263:
259:
250:
246:
244:
241:
240:
230:
203:
200:
199:
177:
174:
173:
150:
147:
146:
115:
112:
111:
95:
92:
91:
88:comparison sort
58:yes–no question
17:
12:
11:
5:
5802:
5792:
5791:
5789:Decision trees
5786:
5781:
5767:
5766:
5735:
5732:
5729:
5728:
5703:
5658:(3): 949–955.
5642:
5622:
5602:
5581:
5521:
5512:
5491:
5472:(4): 385–392.
5440:
5426:
5411:
5382:(4): 778–797.
5363:
5324:
5305:(2): 181–186.
5285:
5270:
5242:
5227:
5207:
5178:(4): 649–659.
5158:
5137:(6): 639–650.
5117:
5088:
5066:
5047:(5): 387–389.
5026:
5025:
5023:
5020:
5019:
5018:
5013:
5008:
5003:
4996:
4993:
4980:
4975:
4971:
4967:
4964:
4961:
4958:
4955:
4952:
4949:
4946:
4943:
4940:
4937:
4910:
4907:
4904:
4901:
4879:
4875:
4854:
4832:
4828:
4807:
4804:
4801:
4798:
4793:
4789:
4785:
4782:
4779:
4774:
4770:
4749:
4729:
4709:
4689:
4669:
4649:
4646:
4643:
4640:
4637:
4617:
4590:
4587:
4584:
4581:
4578:
4575:
4572:
4569:
4566:
4546:
4540:
4537:
4532:
4528:
4525:
4522:
4519:
4516:
4513:
4510:
4507:
4504:
4501:
4481:
4476:
4472:
4468:
4465:
4462:
4459:
4456:
4453:
4450:
4447:
4444:
4441:
4421:
4400:
4397:
4393:
4390:
4363:
4335:
4332:
4329:
4326:
4306:
4286:
4266:
4246:
4226:
4206:
4182:
4179:
4176:
4173:
4170:
4167:
4162:
4158:
4154:
4151:
4148:
4145:
4142:
4139:
4121:Main article:
4118:
4115:
4098:
4095:
4092:
4089:
4069:
4066:
4063:
4058:
4054:
4031:
4027:
4023:
4020:
4017:
4014:
3983:
3978:
3974:
3970:
3967:
3962:
3958:
3954:
3951:
3948:
3945:
3942:
3939:
3936:
3916:
3911:
3907:
3903:
3900:
3895:
3891:
3887:
3884:
3881:
3878:
3875:
3872:
3869:
3849:
3846:
3843:
3840:
3835:
3831:
3827:
3824:
3819:
3815:
3811:
3808:
3803:
3799:
3795:
3792:
3789:
3786:
3783:
3780:
3775:
3771:
3750:
3745:
3741:
3737:
3734:
3729:
3725:
3721:
3718:
3715:
3712:
3709:
3706:
3703:
3683:
3678:
3674:
3670:
3667:
3662:
3658:
3654:
3651:
3648:
3645:
3642:
3639:
3636:
3610:
3606:
3602:
3599:
3594:
3590:
3586:
3583:
3580:
3577:
3574:
3551:
3548:
3545:
3542:
3539:
3536:
3533:
3530:
3527:
3524:
3519:
3515:
3511:
3508:
3505:
3502:
3497:
3493:
3472:
3469:
3466:
3463:
3460:
3457:
3454:
3451:
3448:
3445:
3440:
3436:
3432:
3429:
3426:
3423:
3418:
3414:
3410:
3407:
3404:
3401:
3396:
3392:
3388:
3385:
3382:
3379:
3374:
3370:
3349:
3329:
3317:
3314:
3301:
3297:
3293:
3290:
3287:
3281:
3278:
3272:
3269:
3266:
3263:
3258:
3254:
3233:
3229:
3225:
3222:
3219:
3216:
3213:
3210:
3207:
3204:
3201:
3196:
3192:
3168:
3165:
3162:
3159:
3156:
3153:
3133:
3130:
3127:
3124:
3120:
3116:
3113:
3110:
3107:
3104:
3101:
3098:
3078:
3075:
3072:
3069:
3066:
3063:
3043:
3040:
3036:
3032:
3029:
3026:
3023:
3020:
3017:
3014:
3011:
3008:
2988:
2968:
2965:
2962:
2956:
2953:
2930:
2904:
2900:
2896:
2893:
2890:
2887:
2884:
2881:
2861:
2858:
2855:
2852:
2849:
2846:
2843:
2840:
2837:
2817:
2797:
2794:
2791:
2788:
2785:
2765:
2738:
2735:
2732:
2727:
2723:
2702:
2699:
2696:
2691:
2687:
2662:
2659:
2656:
2651:
2647:
2626:
2623:
2620:
2615:
2611:
2590:
2570:
2567:
2564:
2561:
2540:
2537:
2534:
2529:
2525:
2501:
2497:
2493:
2490:
2487:
2484:
2481:
2478:
2458:
2454:
2450:
2430:
2427:
2424:
2421:
2400:
2397:
2394:
2389:
2385:
2371:
2368:
2355:
2352:
2349:
2346:
2343:
2323:
2303:
2283:
2280:
2277:
2274:
2271:
2268:
2265:
2262:
2259:
2239:
2236:
2233:
2211:
2207:
2203:
2198:
2194:
2171:
2167:
2163:
2160:
2157:
2154:
2151:
2148:
2128:
2125:
2122:
2119:
2116:
2096:
2076:
2053:
2050:
2036:
2033:
2030:
2025:
2021:
1994:
1991:
1988:
1983:
1979:
1948:
1945:
1942:
1937:
1933:
1907:
1903:
1899:
1896:
1893:
1890:
1887:
1884:
1864:
1860:
1856:
1836:
1833:
1830:
1827:
1806:
1803:
1800:
1795:
1791:
1767:
1763:
1746:
1743:
1730:
1710:
1701:complexity of
1685:
1682:
1679:
1676:
1655:
1633:
1629:
1625:
1622:
1619:
1616:
1613:
1610:
1590:
1587:
1584:
1581:
1569:
1566:
1549:
1546:
1543:
1540:
1518:
1514:
1491:
1487:
1483:
1480:
1477:
1474:
1471:
1468:
1448:
1445:
1442:
1439:
1436:
1433:
1428:
1424:
1420:
1417:
1414:
1411:
1408:
1405:
1390:
1387:
1372:
1368:
1347:
1344:
1341:
1338:
1335:
1332:
1329:
1326:
1323:
1301:
1297:
1293:
1288:
1284:
1263:
1260:
1257:
1237:
1234:
1231:
1228:
1208:
1205:
1202:
1199:
1196:
1193:
1188:
1183:
1178:
1175:
1148:
1118:
1096:
1092:
1088:
1083:
1079:
1056:
1052:
1029:
1025:
1001:
997:
991:
987:
981:
976:
973:
970:
966:
961:
956:
952:
929:
925:
921:
918:
915:
910:
906:
883:
878:
873:
870:
855:
852:
835:
832:
829:
826:
823:
803:
800:
797:
777:
754:
751:
748:
745:
742:
737:
733:
696:
693:
690:
687:
684:
679:
675:
671:
668:
665:
662:
659:
656:
653:
650:
647:
642:
638:
617:
614:
594:
591:
571:
551:
548:
545:
542:
539:
536:
533:
530:
527:
502:
499:
495:
474:
445:
441:
437:
432:
428:
405:
401:
397:
392:
388:
365:
361:
357:
352:
348:
325:
321:
317:
312:
308:
285:
281:
277:
274:
271:
266:
262:
258:
253:
249:
229:
226:
213:
210:
207:
187:
184:
181:
161:
157:
154:
134:
131:
128:
125:
122:
119:
99:
15:
9:
6:
4:
3:
2:
5801:
5790:
5787:
5785:
5782:
5780:
5777:
5776:
5774:
5763:
5758:
5754:
5750:
5743:
5738:
5737:
5718:
5714:
5707:
5699:
5695:
5691:
5687:
5683:
5679:
5675:
5671:
5666:
5661:
5657:
5653:
5646:
5638:
5633:
5626:
5618:
5613:
5606:
5597:
5592:
5585:
5577:
5573:
5569:
5565:
5561:
5557:
5552:
5547:
5543:
5539:
5535:
5528:
5526:
5516:
5508:
5504:
5498:
5496:
5487:
5483:
5479:
5475:
5471:
5467:
5466:Combinatorica
5463:
5459:
5455:
5452: ∩
5451:
5444:
5437:
5430:
5422:
5415:
5407:
5403:
5399:
5395:
5390:
5385:
5381:
5377:
5370:
5368:
5359:
5355:
5351:
5347:
5343:
5339:
5335:
5328:
5320:
5316:
5312:
5308:
5304:
5300:
5296:
5289:
5281:
5277:
5273:
5267:
5262:
5257:
5253:
5246:
5238:
5234:
5230:
5228:0-387-96131-3
5224:
5220:
5219:
5211:
5203:
5199:
5195:
5191:
5186:
5181:
5177:
5173:
5169:
5162:
5154:
5150:
5145:
5140:
5136:
5132:
5128:
5121:
5113:
5107:
5099:
5095:
5091:
5085:
5081:
5080:
5073:
5071:
5062:
5058:
5054:
5050:
5046:
5042:
5038:
5031:
5027:
5017:
5014:
5012:
5009:
5007:
5006:Decision tree
5004:
5002:
4999:
4998:
4992:
4973:
4965:
4959:
4953:
4950:
4944:
4938:
4935:
4927:
4922:
4905:
4899:
4877:
4873:
4852:
4830:
4826:
4802:
4796:
4791:
4787:
4783:
4780:
4777:
4772:
4768:
4747:
4727:
4707:
4687:
4667:
4644:
4638:
4635:
4615:
4607:
4602:
4585:
4579:
4576:
4570:
4564:
4538:
4535:
4526:
4520:
4514:
4511:
4505:
4499:
4474:
4466:
4460:
4454:
4451:
4445:
4439:
4419:
4398:
4395:
4391:
4388:
4380:
4375:
4361:
4353:
4349:
4330:
4324:
4304:
4284:
4264:
4244:
4224:
4204:
4196:
4177:
4174:
4171:
4160:
4152:
4149:
4146:
4140:
4137:
4130:
4124:
4114:
4112:
4093:
4087:
4064:
4056:
4052:
4029:
4021:
4018:
4015:
4004:
4000:
3995:
3976:
3968:
3960:
3956:
3949:
3946:
3940:
3934:
3909:
3901:
3893:
3889:
3882:
3879:
3873:
3867:
3841:
3833:
3829:
3825:
3822:
3817:
3809:
3801:
3797:
3790:
3787:
3781:
3773:
3769:
3743:
3735:
3727:
3723:
3716:
3713:
3707:
3701:
3676:
3668:
3660:
3656:
3649:
3646:
3640:
3634:
3626:
3608:
3600:
3592:
3588:
3584:
3578:
3572:
3563:
3549:
3546:
3540:
3534:
3531:
3525:
3517:
3513:
3509:
3503:
3495:
3491:
3470:
3467:
3461:
3455:
3452:
3446:
3438:
3434:
3430:
3424:
3416:
3412:
3408:
3402:
3394:
3390:
3386:
3380:
3372:
3368:
3347:
3327:
3313:
3299:
3295:
3288:
3279:
3276:
3270:
3264:
3256:
3252:
3231:
3227:
3220:
3214:
3211:
3208:
3202:
3194:
3190:
3180:
3166:
3163:
3157:
3151:
3128:
3125:
3122:
3118:
3114:
3108:
3102:
3096:
3076:
3073:
3067:
3061:
3038:
3034:
3030:
3027:
3024:
3018:
3012:
3006:
2986:
2963:
2954:
2951:
2928:
2920:
2902:
2894:
2891:
2888:
2882:
2879:
2856:
2850:
2847:
2841:
2835:
2815:
2792:
2786:
2783:
2763:
2755:
2750:
2733:
2725:
2721:
2697:
2689:
2685:
2676:
2657:
2649:
2645:
2621:
2613:
2609:
2588:
2565:
2559:
2551:
2535:
2527:
2523:
2499:
2491:
2488:
2485:
2479:
2476:
2456:
2452:
2448:
2425:
2419:
2411:
2395:
2387:
2383:
2367:
2350:
2344:
2341:
2321:
2301:
2278:
2272:
2269:
2263:
2257:
2237:
2234:
2231:
2209:
2205:
2201:
2196:
2192:
2169:
2161:
2158:
2155:
2149:
2146:
2123:
2117:
2114:
2094:
2074:
2065:
2063:
2059:
2049:
2047:
2031:
2023:
2019:
2009:
2006:measures the
2005:
1989:
1981:
1977:
1967:
1963:
1959:
1943:
1935:
1931:
1921:
1905:
1897:
1894:
1891:
1885:
1882:
1862:
1858:
1854:
1831:
1825:
1817:
1801:
1793:
1789:
1765:
1761:
1752:
1742:
1728:
1708:
1700:
1696:
1680:
1674:
1653:
1631:
1623:
1620:
1617:
1611:
1608:
1585:
1579:
1565:
1563:
1544:
1538:
1516:
1512:
1489:
1481:
1478:
1475:
1469:
1466:
1459:for an input
1443:
1440:
1437:
1426:
1418:
1415:
1412:
1406:
1403:
1396:
1386:
1370:
1366:
1339:
1333:
1330:
1327:
1299:
1295:
1291:
1286:
1282:
1261:
1258:
1255:
1232:
1226:
1203:
1200:
1197:
1186:
1176:
1173:
1165:
1160:
1146:
1138:
1134:
1132:
1116:
1094:
1090:
1086:
1081:
1077:
1054:
1050:
1027:
1023:
999:
995:
989:
985:
979:
974:
971:
968:
964:
959:
954:
950:
927:
923:
919:
916:
913:
908:
904:
881:
871:
868:
861:
851:
849:
830:
824:
821:
801:
798:
795:
775:
766:
749:
746:
740:
735:
731:
722:
716:
714:
710:
688:
682:
677:
673:
669:
660:
654:
651:
645:
640:
636:
615:
612:
592:
589:
569:
543:
537:
534:
531:
516:
500:
497:
493:
472:
465:
459:
443:
439:
435:
430:
426:
403:
399:
395:
390:
386:
363:
359:
355:
350:
346:
323:
319:
315:
310:
306:
283:
279:
275:
272:
269:
264:
260:
256:
251:
247:
238:
233:
225:
211:
208:
205:
185:
182:
179:
159:
155:
152:
129:
123:
120:
117:
97:
89:
84:
82:
78:
74:
69:
67:
63:
59:
54:
52:
48:
44:
43:decision tree
40:
36:
32:
23:
19:
5755:(1): 21–43,
5752:
5748:
5720:. Retrieved
5716:
5706:
5655:
5651:
5645:
5625:
5605:
5584:
5541:
5537:
5515:
5506:
5469:
5465:
5461:
5457:
5453:
5449:
5443:
5435:
5429:
5420:
5414:
5379:
5375:
5341:
5337:
5327:
5302:
5298:
5288:
5251:
5245:
5217:
5210:
5175:
5171:
5161:
5134:
5130:
5120:
5078:
5044:
5040:
5030:
4923:
4605:
4603:
4378:
4376:
4351:
4194:
4126:
3998:
3996:
3564:
3319:
3181:
2918:
2753:
2751:
2674:
2515:
2375:
2373:
2066:
2055:
2011:
2007:
1969:
1923:
1922:
1781:
1750:
1748:
1698:
1667:
1571:
1561:
1392:
1161:
1136:
1135:
857:
767:
717:
517:
460:
234:
231:
85:
73:lower bounds
70:
65:
61:
55:
50:
46:
34:
28:
18:
4195:sensitivity
2999:satisfying
2828:satisfying
2601:exactly).
1962:Monte Carlo
464:permutation
5773:Categories
5722:2019-07-26
5665:1907.00847
5596:2010.12629
5551:1506.04719
5344:(1): 1–8.
5022:References
4628:, denoted
3625:Noam Nisan
2941:, denoted
2776:, denoted
1601:, for all
1274:such that
5698:195767594
5682:0003-486X
5568:0004-5411
5503:Nisan, N.
5358:0196-6774
5319:0097-5397
5194:0004-5411
5153:0022-0000
5106:cite book
5098:676697295
5061:0002-9890
4926:Hao Huang
4924:In 2019,
4797:⊂
4781:…
4680:over all
4577:≤
4237:over all
4166:→
3826:
3585:≤
3547:≤
3532:≤
3510:≤
3468:≤
3453:≤
3431:≤
3409:≤
3387:≤
3280:~
3271:≥
3215:
3209:≥
3144:whenever
3109:∈
3054:whenever
3019:∈
2955:~
2883:∈
2787:
2480:∈
2235:∈
2150:∈
2118:⊂
1966:Las Vegas
1886:∈
1612:∈
1470:∈
1432:→
1334:
1322:Ω
1192:→
1087:−
965:∑
917:…
872:∈
825:
799:−
741:
709:mergesort
683:
664:Ω
646:
538:
526:Ω
498:−
494:π
473:π
273:…
124:
5576:10214557
5486:45372592
5237:11970840
5202:18605212
4995:See also
4539:′
4399:′
2872:for all
2469:for all
2224:for all
2008:expected
1875:for all
1219:, where
713:heapsort
5734:Surveys
5406:1078168
5280:1499957
4352:average
2250:, then
860:vectors
47:queries
37:is the
5696:
5688:
5680:
5574:
5566:
5484:
5404:
5356:
5317:
5278:
5268:
5235:
5225:
5200:
5192:
5151:
5096:
5086:
5059:
4193:, the
4127:For a
3483:, and
2917:. The
2754:degree
1697:, the
1131:fibers
1129:whose
5745:(PDF)
5694:S2CID
5686:JSTOR
5660:arXiv
5632:arXiv
5612:arXiv
5591:arXiv
5572:S2CID
5546:arXiv
5482:S2CID
5456:from
5402:S2CID
5384:arXiv
5276:S2CID
5198:S2CID
3999:total
2184:, if
378:, or
51:tests
5678:ISSN
5564:ISSN
5464:?".
5454:coNP
5354:ISSN
5315:ISSN
5266:ISBN
5233:OCLC
5223:ISBN
5190:ISSN
5149:ISSN
5112:link
5094:OCLC
5084:ISBN
5057:ISSN
4604:The
4492:and
4377:The
4080:and
3244:and
3089:and
2713:and
2637:and
1042:and
711:and
436:>
396:>
316:<
209:>
183:<
75:for
33:the
5757:doi
5753:288
5670:doi
5656:190
5556:doi
5474:doi
5394:doi
5346:doi
5307:doi
5256:doi
5180:doi
5139:doi
5049:doi
4720:at
4608:of
4277:at
4197:of
3823:log
3277:deg
3212:deg
2952:deg
2921:of
2784:deg
2756:of
2087:at
1331:log
822:log
732:log
674:log
637:log
535:log
198:or
121:log
90:of
64:or
49:or
29:In
5775::
5751:,
5747:,
5715:.
5692:.
5684:.
5676:.
5668:.
5654:.
5570:.
5562:.
5554:.
5542:64
5540:.
5536:.
5524:^
5494:^
5480:.
5468:.
5450:NP
5400:.
5392:.
5380:48
5378:.
5366:^
5352:.
5340:.
5336:.
5313:.
5301:.
5297:.
5274:.
5264:.
5231:.
5196:.
5188:.
5176:19
5174:.
5170:.
5147:.
5133:.
5129:.
5108:}}
5104:{{
5092:.
5069:^
5055:.
5045:66
5043:.
5039:.
4991:.
4921:.
4432:,
4374:.
4113:.
3623:.
3312:.
3179:.
2749:.
2366:.
2048:.
1741:.
1564:.
850:.
458:?
338:,
68:.
5759::
5725:.
5700:.
5672::
5662::
5634::
5614::
5599:.
5593::
5578:.
5558::
5548::
5488:.
5476::
5470:9
5462:A
5458:P
5408:.
5396::
5386::
5360:.
5348::
5342:3
5321:.
5309::
5303:5
5282:.
5258::
5239:.
5204:.
5182::
5155:.
5141::
5135:6
5114:)
5100:.
5063:.
5051::
4979:)
4974:4
4970:)
4966:f
4963:(
4960:s
4957:(
4954:O
4951:=
4948:)
4945:f
4942:(
4939:s
4936:b
4909:)
4906:x
4903:(
4900:f
4878:i
4874:S
4853:x
4831:i
4827:S
4806:]
4803:n
4800:[
4792:t
4788:S
4784:,
4778:,
4773:1
4769:S
4748:t
4728:x
4708:f
4688:x
4668:f
4648:)
4645:f
4642:(
4639:s
4636:b
4616:f
4589:)
4586:f
4583:(
4580:D
4574:)
4571:f
4568:(
4565:s
4545:)
4536:c
4531:)
4527:f
4524:(
4521:D
4518:(
4515:O
4512:=
4509:)
4506:f
4503:(
4500:s
4480:)
4475:c
4471:)
4467:f
4464:(
4461:s
4458:(
4455:O
4452:=
4449:)
4446:f
4443:(
4440:D
4420:f
4396:c
4392:,
4389:c
4362:x
4334:)
4331:x
4328:(
4325:f
4305:x
4285:x
4265:f
4245:x
4225:f
4205:f
4181:}
4178:1
4175:,
4172:0
4169:{
4161:n
4157:}
4153:1
4150:,
4147:0
4144:{
4141::
4138:f
4097:)
4094:f
4091:(
4088:D
4068:)
4065:f
4062:(
4057:0
4053:Q
4030:n
4026:}
4022:1
4019:,
4016:0
4013:{
3982:)
3977:3
3973:)
3969:f
3966:(
3961:0
3957:Q
3953:(
3950:O
3947:=
3944:)
3941:f
3938:(
3935:D
3915:)
3910:4
3906:)
3902:f
3899:(
3894:2
3890:Q
3886:(
3883:O
3880:=
3877:)
3874:f
3871:(
3868:D
3848:)
3845:)
3842:f
3839:(
3834:2
3830:R
3818:2
3814:)
3810:f
3807:(
3802:2
3798:R
3794:(
3791:O
3788:=
3785:)
3782:f
3779:(
3774:0
3770:R
3749:)
3744:2
3740:)
3736:f
3733:(
3728:1
3724:R
3720:(
3717:O
3714:=
3711:)
3708:f
3705:(
3702:D
3682:)
3677:3
3673:)
3669:f
3666:(
3661:2
3657:R
3653:(
3650:O
3647:=
3644:)
3641:f
3638:(
3635:D
3609:2
3605:)
3601:f
3598:(
3593:0
3589:R
3582:)
3579:f
3576:(
3573:D
3550:n
3544:)
3541:f
3538:(
3535:D
3529:)
3526:f
3523:(
3518:0
3514:Q
3507:)
3504:f
3501:(
3496:2
3492:Q
3471:n
3465:)
3462:f
3459:(
3456:D
3450:)
3447:f
3444:(
3439:0
3435:R
3428:)
3425:f
3422:(
3417:1
3413:R
3406:)
3403:f
3400:(
3395:2
3391:R
3384:)
3381:f
3378:(
3373:2
3369:Q
3360:,
3348:f
3328:n
3300:2
3296:/
3292:)
3289:f
3286:(
3268:)
3265:f
3262:(
3257:2
3253:Q
3232:2
3228:/
3224:)
3221:f
3218:(
3206:)
3203:f
3200:(
3195:0
3191:Q
3167:1
3164:=
3161:)
3158:x
3155:(
3152:f
3132:]
3129:1
3126:,
3123:3
3119:/
3115:2
3112:[
3106:)
3103:x
3100:(
3097:p
3077:0
3074:=
3071:)
3068:x
3065:(
3062:f
3042:]
3039:3
3035:/
3031:1
3028:,
3025:0
3022:[
3016:)
3013:x
3010:(
3007:p
2987:p
2967:)
2964:f
2961:(
2929:f
2903:n
2899:}
2895:1
2892:,
2889:0
2886:{
2880:x
2860:)
2857:x
2854:(
2851:p
2848:=
2845:)
2842:x
2839:(
2836:f
2816:p
2796:)
2793:f
2790:(
2764:f
2737:)
2734:f
2731:(
2726:1
2722:Q
2701:)
2698:f
2695:(
2690:0
2686:Q
2661:)
2658:f
2655:(
2650:E
2646:Q
2625:)
2622:f
2619:(
2614:2
2610:Q
2589:f
2569:)
2566:x
2563:(
2560:f
2539:)
2536:f
2533:(
2528:E
2524:Q
2500:n
2496:}
2492:1
2489:,
2486:0
2483:{
2477:x
2457:3
2453:/
2449:2
2429:)
2426:x
2423:(
2420:f
2399:)
2396:f
2393:(
2388:2
2384:Q
2354:)
2351:f
2348:(
2345:C
2342:R
2322:x
2302:f
2282:)
2279:x
2276:(
2273:f
2270:=
2267:)
2264:y
2261:(
2258:f
2238:S
2232:i
2210:i
2206:x
2202:=
2197:i
2193:y
2170:n
2166:}
2162:1
2159:,
2156:0
2153:{
2147:y
2127:]
2124:n
2121:[
2115:S
2095:x
2075:f
2035:)
2032:f
2029:(
2024:1
2020:R
1993:)
1990:f
1987:(
1982:0
1978:R
1947:)
1944:f
1941:(
1936:2
1932:R
1906:n
1902:}
1898:1
1895:,
1892:0
1889:{
1883:x
1863:3
1859:/
1855:2
1835:)
1832:x
1829:(
1826:f
1805:)
1802:f
1799:(
1794:2
1790:R
1766:i
1762:p
1729:f
1709:f
1684:)
1681:f
1678:(
1675:D
1654:f
1632:n
1628:}
1624:1
1621:,
1618:0
1615:{
1609:x
1589:)
1586:x
1583:(
1580:f
1548:)
1545:x
1542:(
1539:f
1517:i
1513:x
1490:n
1486:}
1482:1
1479:,
1476:0
1473:{
1467:x
1447:}
1444:1
1441:,
1438:0
1435:{
1427:n
1423:}
1419:1
1416:,
1413:0
1410:{
1407::
1404:f
1371:2
1367:n
1346:)
1343:)
1340:n
1337:(
1328:n
1325:(
1300:j
1296:x
1292:=
1287:i
1283:x
1262:j
1259:,
1256:i
1236:)
1233:x
1230:(
1227:f
1207:}
1204:1
1201:,
1198:0
1195:{
1187:n
1182:R
1177::
1174:f
1147:d
1117:f
1095:j
1091:x
1082:i
1078:x
1055:j
1051:x
1028:i
1024:x
1000:i
996:x
990:i
986:a
980:n
975:1
972:=
969:i
960:+
955:0
951:a
928:n
924:a
920:,
914:,
909:0
905:a
882:n
877:R
869:x
834:)
831:n
828:(
802:1
796:n
776:n
753:)
750:!
747:n
744:(
736:2
695:)
692:)
689:n
686:(
678:2
670:n
667:(
661:=
658:)
655:!
652:n
649:(
641:2
616:!
613:n
593:!
590:n
570:n
550:)
547:)
544:n
541:(
532:n
529:(
501:1
444:j
440:x
431:i
427:x
404:j
400:x
391:i
387:x
364:j
360:x
356:=
351:i
347:x
324:j
320:x
311:i
307:x
284:n
280:x
276:,
270:,
265:2
261:x
257:,
252:1
248:x
212:b
206:a
186:b
180:a
160:b
156:,
153:a
133:)
130:n
127:(
118:n
98:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
